三分套三分

求$ z = x ^ 2 + y ^2 $的最小值，根据多元函数求偏导，二阶导数大于0，凹函数，存在最小值，有多元函数微分学味了。
固定x，三分求y，一般这样求多个变量的，一般可以先固定一个！

一行语句实现浮点数的四舍五入printf("%d",(int)(check(l) + 0.5)); // 浮点数四舍五入，学到了！
参考资料
时间复杂度$O(logn * logn * n)$

#include <iostream>
#include <cmath>

using namespace std;

const int N = 110;

#define eps 1e-4

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

double dis(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 check(double x1) // 三分y，x和y都是凹函数，结构一样
{
    double l = 0.0,r = 10000.0;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(dis(x1, mid) > dis(x1, mmid)) l = mid;
        else r = mmid; // 这里是r = mmid;
    }
    return dis(x1,l);
}

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> x[i] >> y[i];

    double l = 0.0,r = 10000.0;
    while(r - l > eps)  // 三分x
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(check(mid) > check(mmid)) l = mid;
        else r = mmid; // 这里是r = mmid;
    }

    printf("%d",(int)(check(l) + 0.5)); // 浮点数四舍五入，学到了！

    return 0;
}