本文共 1986 字,大约阅读时间需要 6 分钟。
#include#include #include #include #include using namespace std;#define eps 1e-8int top , n;//点struct POINT{ double x, y; POINT(){ } POINT(double a, double b){ x = a; y = b; }}p[50005],st[50005];//线段struct Seg{ POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; }};//叉乘double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}//多边形面积,需要有顺序,顺(逆)时针。double area(){ double ans = 0; for(int i = 1; i < top; i ++){ ans += cross(p[0], p[i], p[i + 1]); } return ans;}//找凸包基点排序bool cmp0(POINT a, POINT b){ if(a.y < b.y) return true; else if(a.y == b.y && a.x < b.x) return true; return false;}double dis(POINT a,POINT b){ return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );}//极角排序bool cmp1(POINT a, POINT b){ if(cross(p[0], a, b) > eps) return true; else if(fabs(cross(p[0], a, b)) < eps && dis(p[0], a) - dis(p[0], b) > eps) return true; return false;}//Graham_scan 求凸包.所求为纯净凸包...void Graham_scan(){ sort(p, p + n, cmp0); sort(p + 1, p + n, cmp1); top = 0; p[n] = p[0]; st[top ++] = p[0]; st[top ++] = p[1]; for(int i = 2; i <= n; i ++){ while(top > 2 && (cross(st[top - 1], st[top - 2], p[i]) > eps || fabs(cross(st[top - 1], st[top - 2], p[i])) < eps)) top --; st[top ++] = p[i]; } top --;}double dis2(POINT a , POINT b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);}int main(){ while(~scanf("%d",&n)){ for(int i = 0;i < n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); if(n == 2) {printf("%.lf\n",dis2(p[0],p[1]));continue;} Graham_scan(); double _max = 0; for(int i = 0;i < top;i++) for(int j = i+1;j < top;j++) _max = max(_max,dis2(st[i],st[j])); printf("%.0lf\n",_max); }}
转载地址:http://mcsgi.baihongyu.com/