hdu 4717 The Moving Points（第一个三分题）

http://acm.hdu.edu.cn/showproblem.php?pid=4717

【题意】：

给N个点，给出N个点的方向和移动速度，求每个时刻N个点中任意两点的最大值中的最小值，以及取最小值的时刻

【题解】：

两个点为例，任意两个点，按照自己的方向移动，一般情况下是，先两点慢慢接近，直到最近距离，然后慢慢远离，后面越来越远，图像画出来有点像抛物线，

这题就是抛物线求最小值，三分：先二分时间，按照斜率确定移动方向，直到移动到抛物线的最低端

注意题目精度，每次最好分1e-5以上，才能保证正确性

【code】：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <math.h>
 6 //using namespace std;
 7 
 8 #define N 310
 9 #define INF 1e15
10 #define exp 1e-6
11 
12 int n;
13 
14 struct Nod
15 {
16     double x,y;
17     int dx,dy;
18 }node[N];
19 
20 double distance(int i,int j,double k)
21 {
22     return sqrt((double)((node[i].x+k*node[i].dx-node[j].x-k*node[j].dx)*(node[i].x+k*node[i].dx-node[j].x-k*node[j].dx)
23                          +(node[i].y+k*node[i].dy-node[j].y-k*node[j].dy)*(node[i].y+k*node[i].dy-node[j].y-k*node[j].dy)));
24 }
25 
26 double getLargest(double k)
27 {
28     int i,j;
29     double maks = -1,temp;
30     for(i=0;i<n;i++)
31     {
32         for(j=i+1;j<n;j++)
33         {
34             temp = distance(i,j,k);
35             if(maks<temp)
36             {
37                 maks = temp;
38             }
39         }
40     }
41     return maks;
42 }
43 
44 void sanfen()
45 {
46     double l=0,mid,r=1e8,t=INF,ans=INF;
47     while(l<r)
48     {
49         mid = (l+r)/2;  //二分时间
50         double temp1 = getLargest(mid);
51         double temp2 = getLargest(mid-exp);
52         //printf("%lf %lf
",temp1,temp2);
53         if(temp1<temp2)
54         {
55             l=mid+exp;
56         }
57         else
58         {
59             r=mid-exp;
60         }
61         if(ans>temp1)
62         {
63             ans=temp1;
64             t=mid;
65         }
66     }
67     printf("%.2lf %.2lf
",t,ans);
68 }
69 
70 int main()
71 {
72     int t,cas=1;
73     scanf("%d",&t);
74     while(t--)
75     {
76         int i;
77         scanf("%d",&n);
78         for(i=0;i<n;i++)
79         {
80             scanf("%lf%lf%d%d",&node[i].x,&node[i].y,&node[i].dx,&node[i].dy);
81         }
82         printf("Case #%d: ",cas++);
83         sanfen();
84     }
85     return 0;
86 }