三分

[Draymonders]

三分

源于Acwing打卡第一题 3167. 星星还是树

题目通俗讲就是求一个平面内一个点到已知所有点的距离平方和最小

如果固定x的话, 那么关于x的函数将变为常量 f(x)=const 剩余的y的函数为 f(y) = (y1-y)^2 + (y2-y)^2 + ... + (yn-y)^2 = -2y(y1+y2+..+yn) + y^2 + (y1^2+y2^2+...+yn^2)

所以可以看到(y)是个二次凹函数, 因此固定x,找最小的y, 同理固定y,找最小的x

题解

复杂度 O(logn*logn)

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-6;

int n; int xx[110]; int yy[110];

double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

double sum(double x1, double y1) {
    double res = 0;
    for (int i=0; i<n; i++) {
        res += dist(x1, y1, xx[i], yy[i]);
    }
    return res;
}

double get(double x1) {
    double l = 0, r = 10000;
    double res = 1e15;
    while (r-l > eps) {
        double m1 = l + (r-l)/3;
        double m2 = r - (r-l)/3;
        double dis1 = sum(x1, m1);
        double dis2 = sum(x1, m2);
        if (dis1 > dis2) {
            res = dis2;
            l = m1;
        } else {
            res = dis1;
            r = m2;
        }
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i=0; i<n; i++) cin >> xx[i] >> yy[i];
    double l = 0, r = 10000;
    double res = 0.0;
    while (r-l > eps) {
        double m1 = l + (r-l)/3;
        double m2 = r - (r-l)/3;
        double dis1 = get(m1);
        double dis2 = get(m2);
        if (dis1 > dis2) {
            res = dis2;
            l = m1;
        } else {
            res = dis1;
            r = m2;
        }
    }
    cout << (int)(res+0.5) << endl;
    return 0;
}