HDU 4717 The Moving Points 水三分

本文主要是介绍HDU 4717 The Moving Points 水三分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有n个点，每个点朝着不同的方向按照一定的速度前进，在某个时间后，点停下来，可以求得此时任意两点之间的最大距离。问何时停止可以使得任意两点之间的最大距离最小。

想法：三分时间，判断条件是求出k时间情况下，任意两点之间的最大距离就好了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define eps 1e-9
using namespace std;
int n;
struct node
{int x,y,vx,vy;
}dian[305];
double Dis(double a,double b,double c,double d)
{double x=a-c,y=b-d;return sqrt(x*x+y*y);
}
double cal(double mid)
{double maxx=-1;for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){double x1=dian[i].x+mid*dian[i].vx;double y1=dian[i].y+mid*dian[i].vy;double x2=dian[j].x+mid*dian[j].vx;double y2=dian[j].y+mid*dian[j].vy;double dis=Dis(x1,y1,x2,y2);if(dis>maxx) maxx=dis;}}return maxx;
}
int main()
{int test,ca=1;cin>>test;while(test--){cin>>n;for(int i=1;i<=n;i++){cin>>dian[i].x>>dian[i].y>>dian[i].vx>>dian[i].vy;}double lft=0,rht=1000000;while(rht-lft>eps){double mid=(lft+rht)/2;double midd=(mid+rht)/2;if(cal(mid)<cal(midd)){rht=midd;}else lft=mid;}printf("Case #%d: %.2lf %.2lf\n",ca++,lft,cal(lft));} return 0;
}

这篇关于HDU 4717 The Moving Points 水三分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---