题目链接：点我点我 题意：给定n个点。下面n行给出这n个点坐标。 给定m个点，下面m行给出这m个点坐标。 这m个点是一个凸包，顺时针给出的。 问：在凸包上任意找一个点(x, y) 使得这个点距离n个点的距离平方和最小。 问这个最小的距离平方和是多少。
思路： 首先化简一下公式，把变量(x,y)提出来会发现是一个简单的函数，且开口向上，所以有唯一解，解出这个(x,y) 记为 (good_x, good_y)
但这个点可能不是坐落在凸包内，，若坐落在凸包外，则最优解一定是在凸包的边上，所以枚举每条边求个解就好了。 判断点在凸多边形内部用三角形面积相等即可。
;template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != ‘-‘ && (c<‘0′ || c>’9’)) c = getchar();sgn = (c == ‘-‘) ? -1 : 1;ret = (c == ‘-‘) ? 0 : (c – ‘0’);while (c = getchar(), c >= ‘0’&&c <= ‘9’) ret = ret * 10 + (c – ‘0’);ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar(‘-‘);x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + ‘0’);}ll;typedef pair<int, int> pii;const int N = 1e5+10;const int inf = 1e9;const double eps = 1e-4;struct Point{double x, y;Point(double a = 0, double b = 0) :x(a), y(b){}}a[N], b[N];int n, m;double cx, cy, C;double good_x, good_y;double cal(double x, double y){double ans = 0;for (int i = 0; i < n; i++)ans += (a[i].x – x)*(a[i].x – x) + (a[i].y – y)*(a[i].y – y);return ans;}double area(Point x, Point y, Point z){return abs(x.x*y.y + y.x*z.y + z.x*x.y – x.x*z.y – y.x*x.y – z.x*y.y) / 2.0;}double work(Point x){double ans = 0;for (int i = 0; i < m; i++)ans += area(x, b[i], b[(i + 1) % m]);return ans;}double papa(Point x){return n*x.x*x.x + n*x.y*x.y – 2 * x.x*cx – 2 * x.y*cy;}Point cut(Point x, Point y, double k){return Point(x.x + k*(y.x – x.x), x.y + k*(y.y – x.y));}double hehe(Point x, Point y){double ans = min(papa(x), papa(y));if (y.x != x.x){double k = (y.y – x.y) / (y.x – x.x), b = x.y – k*x.x;double _x = (k*cy + cx – n*k*b) / n / (1 + k*k);if (_x < min(x.x, y.x) || _x > max(x.x, y.x))return ans;double _y = k*_x + b;ans = min(ans, papa(Point(_x, _y)));}else {if (min(x.y, y.y) <= good_y && good_y <= max(x.y, y.y))ans = min(ans, papa(Point(x.x, good_y)));}return ans;}int main(){rd(n);cx = cy = C = 0;for (int i = 0; i < n; i++){rd(a[i].x), rd(a[i].y);cx += a[i].x;cy += a[i].y;C += a[i].x*a[i].x + a[i].y*a[i].y;}rd(m);for (int i = 0; i < m; i++)rd(b[i].x), rd(b[i].y);good_x = (double)cx / n;good_y = (double)cy / n;if (abs(work(b[0]) – work(Point(good_x, good_y))) < eps)printf(“%.10f\n”, cal(good_x, good_y));else {double ans = 1e19;for (int i = 0; i < m; i++)ans = min(ans, hehe(b[i], b[(1 + i) % m]));printf(“%.10f\n”, ans + C);}return 0;}
天才是百分之一的灵感加上百分之九十九的努力
