题目链接：
题意：
给定二维坐标上的4个点
问：
找一个点使得这个点距离4个点的距离和最小
输出距离和。
思路：
若4个点不是凸4边形。则一定是端点最优。
否则就是2条对角线的交点最优，能够简单证明一下。
对于凸4边形则先极角排序一下。
#include#include #include #include using namespace std;typedef double ll;const int N = 5;int n = 4;double x[N], y[N];struct Point { ll x, y, dis;} s[4], p0;ll Dis(ll x1, ll y1, ll x2, ll y2){ return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}int Cmp_PolarAngel(struct Point p1, struct Point p2, struct Point pb){ double delta=(p1.x-pb.x)*(p2.y-pb.y)-(p2.x-pb.x)*(p1.y-pb.y); if (delta<0.0) return 1; else if (delta==0.0) return 0; else return -1;}bool Is_LeftTurn(struct Point p3, struct Point p2, struct Point p1){ int type=Cmp_PolarAngel(p3, p1, p2); if (type<0) return true; return false;}int Cmp(const void*p1, const void*p2){ struct Point*a1=(struct Point*)p1; struct Point*a2=(struct Point*)p2; int type=Cmp_PolarAngel(*a1, *a2, p0); if (type<0) return -1; else if (type==0) { if (a1->dis dis) return -1; else if (a1->dis==a2->dis) return 0; else return 1; } else return 1;}double cal(double x1, double y1, double x2, double y2) { return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}int main() { while (~scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x[0], &y[0], &x[1], &y[1], &x[2], &y[2], &x[3], &y[3])) { if(x[0] == -1) break; double ans = 1e10, di; for(int i = 0; i < n; i ++) { di = 0.0; for(int j = 0; j < n; j ++) { if(j == i) continue; di += cal(x[i], y[i], x[j], y[j]); } ans = min(ans, di); } double xx = x[0] + x[1] + x[2] + x[3]; double yy = y[0] + y[1] + y[2] + y[3]; di = 0.0; for(int j = 0; j < n; j ++) { di += cal(xx/4, yy/4, x[j], y[j]); } ans = min(ans, di); p0.x = x[0], p0.y = y[0]; for(int i = 0; i < 4; i ++) { s[i].x = x[i]; s[i].y = y[i]; } for(int i = 0; i < n; i ++) { s[i].dis = cal(s[0].x, s[0].y, s[i].x, s[i].y); } qsort(s+1, n-1, sizeof(struct Point), Cmp); x[0] = s[0].x; y[0] = s[0].y; x[1] = s[2].x; y[1] = s[2].y; x[2] = s[1].x; y[2] = s[1].y; x[3] = s[3].x; y[3] = s[3].y; double k1 = (y[0] - y[1]) / (x[0] - x[1]); double k2 = (y[3] - y[2]) / (x[3] - x[2]); double ansx, ansy; if(x[0] == x[1]) { ansx = x[0]; if(x[2] == x[3]) { ansy = yy / 4; } else { ansy = k2 * (ansx - x[2]) + y[2]; } } else { if(x[2] == x[3]) { ansx = x[2]; ansy = k1 * (ansx - x[1]) + y[1]; } else { if(k1 != k2) { ansx = (y[2] - y[1] + k1*x[1] - k2*x[2]) / (k1 - k2); ansy = k1*(ansx - x[1]) + y[1]; } else { ansx = 1000; ansy = 1000; } } } di = 0.0; for(int j = 0; j < n; j ++) { di += cal(ansx, ansy, x[j], y[j]); } ans = min(ans, di); printf("%.4f\n", ans); } return 0;}