ICPCCamp2017 Day 4 F Factory（三分套三分）

大体题意：

给你二维坐标面上n个点，让你求出一个点，到这n个点的距离和最小？

思路：

赛后才想出怎么做来= =

写一写表达式：

sqrt((x0-x1)^2 + (y0-y1)^2 ) + sqrt((x0-x2)^2 + (y0-y2)^2 ) + sqrt((x0-x3)^2 + (y0-y3)^2 ) ....

观察发现，x0是一个凹凸函数（二次函数）关系，y0也是一个凹凸函数（二次函数）关系，  加起来还是一个二次函数关系（凹凸函数）。

那么两个未知量，都是凹凸性，直接三分x中在三分y即可。

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define sqr(x) ((x)*(x))using namespace std;const double eps = 1e-10;int n, T;int dcmp(double a,double b){    if (fabs(a-b) < eps) return 0;    if (a < b) return -1;    return 1;}struct Node{    double x,y;    void read(){        scanf("%lf %lf",&x, &y);    }}p[1007];double judge(double x,double y){    double sum = 0;    for (int i = 0; i < n; ++i){        double xx = p[i].x;        double yy = p[i].y;        sum += sqrt(sqr(x-xx) + sqr(y-yy));    }    return sum;}const int oo = 1e6+7;int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for (int i = 0; i < n; ++i) p[i].read();        double lx = -oo, rx = oo;        double ly = -oo, ry = oo;        for (int i = 0; i < 100; ++i){            ly = -oo, ry = oo;            double mx1 = (rx+lx) / 2;            double mx2 = (mx1 + rx) / 2;            for (int j = 0; j < 100; ++j){                double my1 = (ly + ry) / 2;                double my2 = (my1 + ry) / 2;                double t1 = judge(mx1,my1);                double t2 = judge(mx1,my2);                if (dcmp(t1,t2) == -1) ry = my2;                else ly = my1;            }            double ny1 = (ly+ry) / 2;            ly = -oo, ry = oo;            for (int j = 0; j < 100; ++j){                double my1 = (ly + ry) / 2;                double my2 = (my1 + ry) / 2;                double t1 = judge(mx2,my1);                double t2 = judge(mx2,my2);                if (dcmp(t1,t2) == -1) ry = my2;                else ly = my1;            }            double ny2 = (ly+ry) / 2;            double nt1 = judge(mx1,ny1), nt2 = judge(mx2,ny2);            if (dcmp(nt1,nt2) == -1) rx = mx2;            else lx = mx1;        }        PRintf("%.10f %.10f/n",(lx+rx)/2,(ly+ry)/2);    }    return 0;}/**13-3 00 33 0**/