3933 - 雷达
时间限制 : 1 秒
内存限制 : 128 MB
国王张静静的国家发生了战乱。为了平定战乱，张静静开发出一种新型的雷达，要用这种雷达来侦测一个平面上的 n 个飞机的动向。
假设雷达安装在 O(x0,y0) 位置，n 个飞机坐落在 P1(x1,y1),P2(x2,y2),...,Pn(xn,yn) 。雷达对于每个 Pi(i=1,2,3,...,n) ，会侦测该位置的飞机是否跟雷达的距离发生变化，如果变化，雷达就会报警。
为了做到这一点，张静静的雷达的工作原理是这样的：雷达对于每个 Pi(i=1,2,3,...,n) 会发出一种神奇的物质 Ω ，布满以 O 为圆心，以 OPi 为半径的球表面（这个球有一半是在底下的，雷达实际发出 Ω 布满的部分是球表面积的一半）。如果飞机穿过了 Ω 层，雷达就会得到反馈。
注意，雷达是不够智能的，即使O 距离几个敌军飞机距离相同，Ω 层也不会共用。
所以张静静的问题就是，如何合理的安排雷达的位置，使得 Ω 层总面积最小？
题目输入
测试数据有多组，数据第一行包含测试数据的数目 T(≤10) 。
每组数据第一行包含一个整数 n(1≤n≤100000)，意义见题目描述。
接下来 n 行，第 i(i=1,2,3,...,n) 行有两个数 (xi,yi) 表示第 i 个飞机的位置坐标。
数据保证不会有两个飞机的距离小于 0.001 。
题目输出
对于每组测试数据，输出 v于一行，表示最小的花费，保留小数点后三位小数。
输入/输出样例
输入格式
1 2 1 1 2 2
输出格式
6.283
C++解答
#include <stdio.h> #include <math.h> const int MAXN = 100000 + 5; const double PI = acos(-1.0); double xi[MAXN]; double yi[MAXN]; double sqr(double x) { return x * x; } int main() { int casc; scanf("%d", &casc); for (int casi = 1; casi <= casc; casi++) { int n; scanf("%d", &n); double x = 0; double y = 0; for (int i = 0; i < n; i++) { scanf("%lf %lf", &xi[i], &yi[i]); x += xi[i]; y += yi[i]; } x /= n; y /= n; double res = 0; for (int i = 0; i < n; i++) res += sqr(x - xi[i]) + sqr(y - yi[i]); res *= PI * 2; printf("%.3f\n", res); } return 0; }