题目描述

在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)。

请你找出一个点，使得该点到这 n 个点的距离之和最小。

该点可以选择在平面中的任意位置，甚至与这 n 个点的位置重合。

样例

输入样例：
4
0 0
0 10000
10000 10000
10000 0

输出样例：
28284

算法

(三分套三分)

• 距离最小点在多边形内部
• 先三分x维度，然后在三分x维的基础上三分y维度

时间复杂度 $O(n\*logn\*logn)$

参考文献

https://www.cnblogs.com/lfri/p/11604701.html

C++ 代码

#include<cstdio>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;

const int N = 10010;
const double eps = 1e-4;

int n;
double x[N], y[N];

double dis1(double x1, double y1)
{
    double sum = 0.0;
    for(int i=0;i<n;i++){
        sum += sqrt((x[i] - x1)*(x[i] - x1) + (y[i] - y1) * (y[i] - y1));
    }

    return sum;
}

double dis(double x1)
{
    double l = 0.0, r = 10000.0;
    int i = 0;
    while(r - l >= eps){
        double margin = (r - l)/3.0;
        double m1 = l + margin;
        double m2 = m1 + margin;
        if(dis1(x1, m1) <= dis1(x1, m2)) r = m2;
        else l = m1;
    }

    return dis1(x1, l);
}


int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf", &x[i], &y[i]);
    }

    double l = 0.0, r = 10000.0;
    while(r - l >= eps){
        double margin = (r - l) / 3.0;
        double m1 = l + margin;
        double m2 = m1 + margin;
        if(dis(m1) <= dis(m2)) r = m2;
        else l = m1;
    }

    printf("%d", (int)(dis(l)+0.5));
}