链接:http://acm.hdu.edu.cn/showproblem.php?pid=4717
n个点,给出初始坐标和移动的速度和移动的方向,求在哪一时刻任意两点之间的距离的最大值的最小。
对于最大值的最小问题首先就会想到二分,然而由于两点之间的距离是呈抛物线状,所以三分的方法又浮上脑海,当然二分也可以做,不过思维上更复杂一些
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const double eps = 0.000001;
const int M = ;
int n; struct point{
double x,y,vx,vy;
void read(){scanf("%lf%lf%lf%lf",&x,&y,&vx,&vy);}
}po[M]; double max(double x,double y){return x>y?x:y;} double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} double cal(double t)
{
double ans=;
for (int i= ; i<=n ; i++){
for (int j=i+ ; j<=n ; j++){
double num=dis(po[i].x+t*po[i].vx,po[i].y+t*po[i].vy,po[j].x+t*po[j].vx,po[j].y+t*po[j].vy);
ans=max(num,ans);
}
}
return ans;
} double solve(double l,double r)
{
while (r-l>=eps)
{
double mid1=(l*+r)/;
double mid2=(l+r*)/;
if (cal(mid2)-cal(mid1)>eps)
r=mid2;
else
l=mid1;
}
return l;
} int main()
{
int t,cas=;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i= ; i<=n ; i++)
po[i].read();
double ans=solve(,1e8);
printf("Case #%d: ", ++cas);
if (n==) printf("0.00 0.00\n");
else printf("%.2lf %.2lf\n",ans,cal(ans));
}
return ;
}