hdu 2440 Watch out the Animal(凸包+费马点) - c++编程基础

读懂了题的话就不难发现是要求费马点，不过输入点的顺序是不一定的，而且求的是凸包的费马点，不是所有点的费马点。。。
 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;  
        ch[m++] = p[i];  
    }  
    int k = m;  
    FD(i, n-2, 0)  
    {  
        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;  
        ch[m++] = p[i];  
    }  
    if(n > 1) m--;  
    return m;  
}  
  
inline double dist(Point a, Point b)  
{  
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));  
}  
  
double fermat_point(Point *pt, int n, Point& ptres)  
{  
    Point u, v;  
    double step = 0.0, curlen, explen, minlen;  
    int i, j, k, idx;  
    bool flag;  
    u.x = u.y = v.x = v.y = 0.0;  
    REP(i, n)  
    {  
        step += fabs(pt[i].x) + fabs(pt[i].y);  
        u.x += pt[i].x;  
        u.y += pt[i].y;  
    }  
    u.x /= n;  
    u.y /= n;  
    flag = 0;  
    while(step > eps)  
    {  
        for(k = 0; k < 10; step /= 2, ++k)  
            for(i = -1; i <= 1; ++i)  
                for(j = -1; j <= 1; ++j)  
                {  
                    v.x = u.x + step*i;  
                    v.y = u.y + step*j;  
                    curlen = explen = 0.0;  
                        REP(idx, n)  
                    {  
                        curlen += dist(u, pt[idx]);  
                        explen += dist(v, pt[idx]);  
                    }  
                    if(curlen > explen)  
                    {  
                        u = v;  
                        minlen = explen;  
                        flag = 1;  
                    }  
                }  
    }  
    ptres = u;  
    return flag   minlen : curlen;  
}  
  
int main()  
{  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d", &n);  
        REP(i, n) scanf("%lf%lf", &p[i].x, &p[i].y);  
        int m = ConvexHull(p, n, pt);  
        double ans = fermat_point(pt, m, ft);  
        printf("%.0f\n", ans);  
        if(T > 0) puts("");  
    }  
    return 0;  
}