UVA11796 Dog Distance 計算幾何

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

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.Bkjia.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