大體題意：

給你二維坐標面上n個點，讓你求出一個點，到這n個點的距離和最小？

思路：

賽后才想出怎么做來= =

寫一寫表達式：

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

觀察發(fā)現(xiàn)，x0是一個凹凸函數(shù)（二次函數(shù)）關(guān)系，y0也是一個凹凸函數(shù)（二次函數(shù)）關(guān)系，  加起來還是一個二次函數(shù)關(guān)系（凹凸函數(shù)）。

那么兩個未知量，都是凹凸性，直接三分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**/