UVALive 4728 Squares

https://vjudge.net/problem/UVALive-4728

题意 ：

给出n个正方形，求所有的正方形顶点中的最远距离

求凸包直径，旋转卡壳

开始狂WA原因：

返回凸包中点的个数时，返回的m

凸包中点实际为[0,m-2]，

m-1位置（上凸壳加进去的）与0位置（下凸壳加进去的）相同

在旋转卡壳时，q的取值范围为[0,m-1]

但会用到m，此时的m位置不是凸包中的点

所以令m-1

凸包中点实际为[0,m-1]

m位置（上凸壳加进去的）与0位置（下凸壳加进去的）相同

在旋转卡壳时，q取值范围[0,m-1]

q最大用到m，m位置仍是凸包中的点

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define N 400001

using namespace std;

struct Point
{
    int x,y;
    
    Point (int x=0,int y=0):x(x),y(y) { }

    bool operator < (Point p) const
    {
        if(x!=p.x) return x<p.x;
        return y<p.y;
    }
    
    bool operator == (Point p) const
    {
        return x==p.x && y==p.y;
    }
};

typedef Point Vector;

Point P[N],ch[N];

Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}

int ConvexHull(Point *p,int n,Point *c)
{
    sort(p,p+n);
    n=unique(p,p+n)-p;
    int m=0;
    for(int i=0;i<n;++i)
    {
        while(m>1 && Cross(c[m-1]-c[m-2],p[i]-c[m-2])<=0) m--;
        c[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;--i)
    {
        while(m>k && Cross(c[m-1]-c[m-2],p[i]-c[m-2])<=0) m--;
        c[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}

int getdis(Point A,Point B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

int RotatingCaliper(Point *c,int m)
{
    int q=1;
    int ans=0;
    for(int p=0;p<m;++p)
    {
        while(abs(Cross(c[p]-c[p+1],c[q+1]-c[p+1]))>abs(Cross(c[p]-c[p+1],c[q]-c[p+1]))) q=(q+1)%m;
        ans=max(ans,max(getdis(c[p],c[q]),getdis(c[p+1],c[q+1])));
        ans=max(ans,max(getdis(c[p+1],c[q]),getdis(c[p],c[q+1])));
    }
    return ans;
}

int main()
{
    int T,n,m;
    int cnt,x,y,w;
    read(T);
    while(T--)
    {
        read(n);
        cnt=0;
        for(int i=1;i<=n;++i)
        {
            read(x); read(y); read(w);
            P[cnt].x=x; P[cnt++].y=y;
            P[cnt].x=x+w; P[cnt++].y=y;
            P[cnt].x=x; P[cnt++].y=y+w;
            P[cnt].x=x+w; P[cnt++].y=y+w;
        }
        m=ConvexHull(P,cnt,ch);
        printf("%d
",RotatingCaliper(ch,m));
    }
}