题目地址：POJ 2187
凸包第一发。。用的大白书上的andew算法。
先求出凸包，然后最大距离一定是凸包之中的某两点之间的距离，然后枚举找出最大值。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const int INF=0x3f3f3f3f; int top, n; struct Point { int x, y; }p[100000], tu[100000]; int dist(Point x, Point y) { return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y); } Point operator - (Point x, Point y) { Point z; z.x=x.x-y.x; z.y=x.y-y.y; return z; } int Cross(Point x, Point y) { return x.x*y.y-x.y*y.x; } int cmp(Point x, Point y) { if(x.x==y.x) return x.y y?x:y; } void Andew() { int i, j, k; sort(p,p+n,cmp); top=0; for(i=0;i 1&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<=0) top--; tu[top++]=p[i]; } k=top; for(i=n-2;i>=0;i--) { while(top>k&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<=0) top--; tu[top++]=p[i]; } int max1=-1; for(i=0;i