正文
HDU 4717 The Moving Points(三分)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4717
题意：给出n个点的坐标和运动速度（包括方向）。求一个时刻t使得该时刻时任意两点距离最大值最小。
思路：每两个点之间的距离随时间的变化是一个开口向上的抛物线。把所有的抛物线画出来。然后每个时刻取最大值。发现这个最大值是单峰函数。
struct point{ double x,y; void get() { RD(x,y); } point(){} point(double _x,double _y) { x=_x; y=_y; } point operator+(point a) { return point(x+a.x,y+a.y); } point operator-(point a) { return point(x-a.x,y-a.y); } point operator*(double a) { return point(x*a,y*a); } double len() { return sqrt(x*x+y*y); }};point s[N],d[N];int n;double cal(double t){ point p[N]; int i; FOR1(i,n) p[i]=s[i]+d[i]*t; double ans=0; int j; FOR1(i,n) FOR(j,i+1,n) upMax(ans,(p[i]-p[j]).len()); return ans;}double cal(){ double L=0,R=1e8,M1,M2; while(R-L>EPS) { M1=(L+R)/2; M2=(M1+R)/2; if(cal(M1)<cal(M2)) R=M2; else L=M1; } return L;}int main(){ int num=0; rush() { RD(n); int i; FOR1(i,n) s[i].get(),d[i].get(); if(n==1) { printf("Case #%d: 0.00 0.00\n",++num); continue; } double t=cal(); printf("Case #%d: %.2lf %.2lf\n",++num,t,cal(t)); }}
