UVALive 5102 Fermat Point in Quadrangle 极角排序+找距离二维坐标4个点最近的点

题目链接：点击打开链接

题意：

给定二维坐标上的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;
}