?
大致题意：给出每个点的坐标以及每个点移动的速度和方向。问在那一时刻点集中最远的距离在所有时刻的最远距离中最小。
比赛时一直以为是计算几何，和线段相交什么的有关。赛后队友说这是道三分，仔细想了想确实是三分，试着画画图发现它是一个凸性函数，存在一个最短距离。然后三分时间就可以了。
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 310; const int INF = 0x3f3f3f3f; struct node { double x,y,vx,vy; }p[maxn],tp[maxn]; int n; double mindis,time; double dis(node a, node b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } double cal(double t) { for(int i = 1; i <= n; i++) { tp[i].x = p[i].x + t * p[i].vx; tp[i].y = p[i].y + t * p[i].vy; } double Max = -1.0; for(int i = 1; i < n; i++) { for(int j = i+1; j <= n; j++) { double ans = dis(tp[i], tp[j]); if(Max < ans) Max = ans; } } return Max; } void solve() { double low = 0, high = INF, mid,midmid; while(high - low > eps) { mid = (high + low)/2; midmid = (mid + high)/2; double ans1 = cal(mid); double ans2 = cal(midmid); if(ans1 > ans2) low = mid; else high = midmid; } time = low; mindis = cal(low); } int main() { int test; scanf(%d,&test); for(int item = 1; item <= test; item++) { scanf(%d,&n); for(int i = 1; i <= n; i++) scanf(%lf %lf %lf %lf,&p[i].x, &p[i].y, &p[i].vx,&p[i].vy); solve(); printf(Case #%d: %.2lf %.2lf ,item,time,mindis); } return 0; }