题目描述

3167.星星还是树(二维寻找一个点使得这个点到其他点距离的总和最小)

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

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

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

输入格式
第一行包含一个整数 n。

接下来 n 行，每行包含两个整数 xi,yi，表示其中一个点的位置坐标。

输出格式
输出最小距离和，答案四舍五入取整。

数据范围
1≤n≤100,
0≤xi,yi≤10000

样例

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


输出样例：
28284

参考文献

https://www.acwing.com/solution/content/29849/

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

C++ 代码

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

const int N = 110;

int x[N],y[N];

int n;

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

double dist(double x)
{
    //y坐标三分
    double l = 0;
    double r = 10000;
    while(r - l >= 1e-4)
    {
        double mid = (l +r)/ 2;
        double mmid = (mid +r) / 2;
        if(dist1(x,mid) < dist1(x,mmid))
        {
            r = mmid;
        }
        else
        {
            l = mid;
        }
    }
    return dist1(x,l);
}

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

    //x坐标三分
    double l = 0;
    double r = 10000;
    while(r - l >= 1e-4)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(dist(mid) < dist(mmid))
        {
            r = mmid;
        }
        else
        {
            l = mid;
        }
    }

    printf("%d\n",(int)(dist(l) + 0.5));
    return 0;
}