当前位置：首页 -> 基础 -> c++编程基础

UVA11796 Dog Distance 计算几何

2015-01-27 18:06:18 · 作者: · 浏览: 53
标签: UVA11796 Dog Distance 计算 几何


计算几何：

题解转自:点击打开链接

首先我们想一下如果甲乙都仅沿着两条线段向前跑,那么他们之间的最短和最长距离怎么算? 假设甲的速度向量为v1(速度向量指甲单位时间所走的位移向量),乙的速度向量为v2. 那么可以把甲看成是静止不动的,而让乙一个人以v2-v1的速度向量去运动(画图验证下).

且假设甲和乙都运动了t秒时间,那么我们可以知道上面的过程类似于甲不动,乙从自己的起点运动了t*(v2-v1)的位移向量. 而乙已知起点和位移向量,那么它就是在一条线段上. 最终我们要求的就是甲这个不动的点到乙这条线段的最大和最小距离即可.(仔细体会下)

下面我们回到原问题. 原问题是一段一段的线段连接起来的折线,但是在某一段时刻,甲乙必然都是同时在走直线段的.

我们只要把握住甲乙的当前点和下一个拐点这两个信息即可.

假设当前甲在Pa点,乙在Pb点.而他们的下一个拐点是Sa和Sb,(由于总距离已知且他们花的时间相同,所以他们的速度va和vb已知).

所以我们可以知道到底甲先到拐点还是乙先到拐点,那么他们在到达拐点的这段时间内就都是走的直线段. 然后我们处理这段的最大最小值.接着更新他们的当前位置点和下一个拐点即可接着循环处理,一直到终点.



Dog Distance
Time Limit: 2000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu

Submit Status

Description

Download as PDF

C

Dog Distance

Input

Standard Input

Output

Standard Output

\

Two dogs, Ranga and Banga, are running randomly following two different paths. They both run for T seconds with different speeds. Ranga runs with a constant speed of R m/s, whereas Banga runs with a constant speed of S m/s. Both the dogs start and stop at the same time. Let D(t) be the distance between the two dogs at time t.

The dog distance is equal to the difference between the maximum and the minimum distance between the two dogs in their whole journey.

Mathematically,<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHN0cm9uZz5Eb2cgRGlzdGFuY2U8L3N0cm9uZz4gPSA8c3Ryb25nPnttYXggKEQoYSkpIDAgPD0gYSA8PSBUfSCoQyB7bWluIChEKGIpKSAgMCA8PSBiIDw9IFR9PC9zdHJvbmc+PC9wPgo8cD5HaXZlbiB0aGUgcGF0aHMgb2YgdGhlIHR3byBkb2dzLCB5b3VyIGpvYiBpcyB0byBmaW5kIHRoZSBkb2cgZGlzdGFuY2UuPC9wPgo8cD5FYWNoIHBhdGggd2lsbCBiZSByZXByZXNlbnRlZCB1c2luZyA8c3Ryb25nPjxlbT5OPC9lbT48L3N0cm9uZz4gcG9pbnRzLCAoPHN0cm9uZz48ZW0+UDxzdWI+MTwvc3ViPiBQPHN1Yj4yPC9zdWI+IFA8c3ViPjM8L3N1Yj4gLi4uIFA8c3ViPk48L3N1Yj48L2VtPjwvc3Ryb25nPikuIFRoZSBkb2cgZm9sbG93aW5nIHRoaXMgcGF0aCB3aWxsIHN0YXJ0IGZyb20gPHN0cm9uZz48ZW0+UDxzdWI+MTwvc3ViPjwvZW0+PC9zdHJvbmc+IGFuZCBmb2xsb3cKIHRoZSBsaW5lIGpvaW5pbmcgd2l0aDxzdHJvbmc+PGVtPlA8c3ViPjI8L3N1Yj48L2VtPjwvc3Ryb25nPiwgYW5kIHRoZW4gaXQgd2lsbCBmb2xsb3cgdGhlIGxpbmUgam9pbmluZyA8c3Ryb25nPjxlbT5QPHN1Yj4yPC9zdWI+LVA8c3ViPjM8L3N1Yj48L2VtPjwvc3Ryb25nPiwgdGhlbiA8c3Ryb25nPjxlbT5QPHN1Yj4zPC9zdWI+LVA8c3ViPjQ8L3N1Yj48L2VtPjwvc3Ryb25nPiBhbmQgc28gb24gdW50aWwgaXQgcmVhY2hlcyA8c3Ryb25nPjxlbT5QPHN1Yj5uPC9zdWI+PC9lbT48L3N0cm9uZz4uPC9wPgo8aDI+SW5wdXQ8L2gyPgo8cD5JbnB1dCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIDxzdHJvbmc+PGVtPkk8L2VtPig8ZW0+SaHcPC9lbT4xMDAwKTwvc3Ryb25nPiwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjwvcD4KPHA+RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggMiBwb3NpdGl2ZSBpbnRlZ2VycyA8c3Ryb25nPjxlbT5BPC9lbT4oMqHcPGVtPkGh3DwvZW0+NTApLDxlbT5CPC9lbT4oMqHcPGVtPkKh3DwvZW0+NTApPC9zdHJvbmc+LiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBjb29yZGluYXRlcyBvZiA8c3Ryb25nPjxlbT5BPC9lbT48L3N0cm9uZz4gcG9pbnRzIHdpdGggdGhlIGZvcm1hdCA8c3Ryb25nPjxlbT5YPHN1Yj4xIDwvc3ViPlk8c3ViPjEgPC9zdWI+WDxzdWI+MiA8L3N1Yj5ZPHN1Yj4yPC9zdWI+IC4uLlg8c3ViPkE8L3N1Yj4gWTxzdWI+QTwvc3ViPjwvZW0+PC9zdHJvbmc+LCA8c3Ryb25nPigwodw8ZW0+WDxzdWI+aTwvc3ViPixZPHN1Yj5pPC9zdWI+PC9lbT6h3DEwMDApPC9zdHJvbmc+LgogVGhlc2UgcG9pbnRzIGluZGljYXRlIHRoZSBwYXRoIHRha2VuIGJ5IFJhbmdhLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIDxzdHJvbmc+PGVtPkI8L2VtPjwvc3Ryb25nPiBwb2ludHMgaW4gdGhlIHNhbWUgZm9ybWF0LiBUaGVzZSBwb2ludHMgaW5kaWNhdGUgdGhlIHBhdGggdGFrZW4gYnkgQmFuZ2EuIEFsbCBkaXN0YW5jZSB1bml0cyBhcmUgZ2l2ZW4gaW4gbWV0ZXJzIGFuZCBjb25zZWN1dGl2ZSBwb2ludHMgYXJlIGRpc3RpbmN0LiBBbGwgdGhlCiBnaXZlbiBjb29yZGluYXRlcyBhcmUgaW50ZWdlcnMuPC9wPgo8cD5Ob3RlIHRoYXQgdGhlIHZhbHVlcyBvZiA8c3Ryb25nPjxlbT5UPC9lbT48L3N0cm9uZz4sIDxzdHJvbmc+PGVtPlI8L2VtPjwvc3Ryb25nPiBhbmQgPHN0cm9uZz48ZW0+UzwvZW0+PC9zdHJvbmc+IGFyZSB1bmtub3duIHRvIHVzLjwvcD4KPGgyPk91dHB1dDwvaDI+CjxwPkZvciBlYWNoIGNhc2UsIG91dHB1dCB0aGUgY2FzZSBudW1iZXIgZmlyc3QuIFRoZW4gb3V0cHV0IHRoZSBkb2cgZGlzdGFuY2Ugcm91bmRlZCB0byB0aGUgbmVhcmVzdCBpbnRlZ2VyLiBMb29rIGF0IHRoZSBzYW1wbGVzIGZvciBleGFjdCBmb3JtYXQuPC9wPgo8cD4gPC9wPgo8cD4gPC9wPgo8dGFibGUgYm9yZGVyPQ=="0" cellspacing="0" cellpadding="0">

Sample Input

Sample Output

2

2 2

0 0 10 0

0 1 10 1

3 2

635 187 241 269 308 254

117 663 760 413

Case 1: 0

Case 2: 404

Source


Root :: Prominent Problemsetters :: Sohel Hafiz
Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 4. Geometry :: Geometric Computations in 2D :: Examples

Submit Status

\ 



#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const double eps=1e-8; int dcmp(double x) { if(fabs(x)
       
        0) return Lenth(v3); else return fabs(Cross(v1,v2))/Lenth(v1); } int n,m; Point aa[55],bb[55]; double LenA,LenB; double MX,MI; void update(Point P,Point A,Point B) { MI=min(MI,DistanceToSegment(P,A,B)); MX=max(MX,max(Lenth(P-A),Lenth(P-B))); } int main() { int T_T,cas=1; scanf("%d",&T_T); while(T_T--) { LenA=0,LenB=0; scanf("%d%d",&n,&m); for(int i=0;i