本文共 2062 字，大约阅读时间需要 6 分钟。
题意：给你一个数据范围在2~5e4范围内的横纵坐标在-1e4~1e4的点，问你任意两点之间的距离的最大值的平方等于多少？
一道卡壳凸包的模板题，也是第一次写计算几何的题，就看了些模板，关于;我是直接找到左下角的点，排好序之后，就直接形成凸包，之后调用rotating_calipers()求解；里面注意在凸包构造好之后，因为是++top的，所以在后面卡壳里面%top会出现问题，所以循环之后再一次++top;开始看graham()里面的while循环看了很久，其实就是维护一个逆时针旋转单调栈，还有一点就是在卡壳里面的while循环里面，为什么直接对q递增，之后%top;能过证明当三角形面积(叉乘)在增大时，边长也在增大；
本文参考
// 110ms#include #include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXN = 5e4+10;struct point{ int x,y; point(){} point(int _x,int _y){ x = _x; y = _y; } int operator *(const point &b)const{ return (x*b.y - y*b.x); } point operator -(const point &b)const{ return point(x - b.x,y - b.y); } void input(){ scanf("%d%d",&x,&y); }}p[MAXN];int dist2(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}bool cmp(point a,point b) // 正表示逆时针，返回true表示不要交换；{ int cp = (a-p[0])*(b-p[0]); if(cp < 0) return false; if(cp == 0 && (dist2(a,p[0]) >= dist2(b,p[0])) ) return false; return true;}int stk[MAXN],top;void graham(int n) // 形成凸包；{ int i; stk[0] = 0;stk[1] = 1; top = 1; for(i = 2;i < n;i++){ // 构造一个逆时针旋转的单调栈； while(top > 0 && (p[stk[top]] - p[stk[top-1]])*(p[i] - p[stk[top-1]]) <= 0) top--; stk[++top] = i; } stk[++top] = 0;//为了下面%top，很容易知道n-1号元素一定在凸包里面； /*for(i=0;i < top;i++){ point tmp = p[stk[i+1]] - p[stk[i]]; while((tmp * (p[stk[q+1]] - p[stk[i]])) > (tmp * (p[stk[q]] - p[stk[i]]))) // 叉积与面积和边长的关系； q = (q+1)%top; ans = max(ans,max(dist2(p[stk[i+1]],p[stk[q+1]]),dist2(p[stk[i]],p[stk[q]])));//最好的是i&&q,但是有平行的情况，so:max } return ans;}int main(){ int i,n; while(scanf("%d",&n) == 1){ for(i = 0;i < n;i++) p[i].input(); int st = 0; for(i = 1;i < n;i++) //选出起始点； if(p[st].y > p[i].y||(p[st].y == p[i].y && p[st].x > p[i].x)) st = i; swap(p[0],p[st]); sort(p+1,p+n,cmp);//以p[0]为参考点逆时针极角由近到远排序； graham(n); printf("%d\n",rotating_calipers()); } return 0;}
转载于:https://www.cnblogs.com/hxer/p/5185154.html
