题目大意：给出n个点，每一个点有初始的位置(x,y),以及单位时间内移动的距离，向量形式给出。且在哪一个时刻中，n个点之间两两距离的最大值最小，最小值为多少。
解题思路：类似与二分算法的三分，由于假设将时间t和所要求的两两之间距离的最大值d做成一个函数曲线，单调性应该是先递减后递增的，所以用三分法求极值。
#include#include #include #include using namespace std;const int N = 305;const double eps = 1e-6;struct point { double x; double y;}s[N], p[N];int n;void init () { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf%lf%lf%lf", &s[i].x, &s[i].y, &p[i].x, &p[i].y);}inline double dis (double x, double y) { return sqrt(x*x+y*y);}double cat (double k) { double ans = 0; for (int i = 0; i < n; i++) { double xi = s[i].x + p[i].x * k; double yi = s[i].y + p[i].y * k; for (int j = i + 1; j < n; j++) { double pi = s[j].x + p[j].x * k; double qi = s[j].y + p[j].y * k; ans = max(ans, dis(xi-pi, yi-qi)); } } return ans;}void solve () { double l = 0; double r = 0xffffff; while (fabs(r-l) > eps) { double tmp = (r-l)/3; double midl = l + tmp; double midr = r - tmp; if (cat(midl) < cat(midr)) r = midr; else l = midl; } printf("%.2lf %.2lf\n", l, cat(l));}int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init (); printf("Case #%d: ", i); solve(); } return 0;}