题目链接：点击打开链接

题意：

给定二维坐标上的4个点

问：

找一个点使得这个点距离4个点的距离和最小

输出距离和。

思路：

若4个点不是凸4边形。则一定是端点最优。

否则就是2条对角线的交点最优，能够简单证明一下。

对于凸4边形则先极角排序一下。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

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<a2->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;

}