UVa1453或La4728 凸包+枚举（或旋转卡壳）

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4199

没想透为啥旋转卡壳跟枚举跑时间差不多。n太小吧！

枚举法：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = ;

const int maxe = ;

const int INF = 0x3f3f3f;

const double eps = 1e-;

const double PI = acos(-1.0);

struct Point{

    double x,y;

    Point(double x=, double y=) : x(x),y(y){ }    //构造函数

};

typedef Point Vector;

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

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

Vector operator * (Vector A , double p){return Vector(A.x*p,A.y*p);}

Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){

    return a.x < b.x ||( a.x == b.x && a.y < b.y);

}

int dcmp(double x){

    if(fabs(x) < eps) return ;

    else              return x <  ? - : ;

}

bool operator == (const Point& a, const Point& b){

    return dcmp(a.x - b.x) ==  && dcmp(a.y - b.y) == ;

}

///向量（x,y）的极角用atan2(y,x);

double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }

double Length(Vector A)    { return Dot(A,A); }

double Angle(Vector A, Vector B)  { return acos(Dot(A,B) / Length(A) / Length(B)); }

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

//凸包：

/**Andrew算法思路：首先按照先x后y从小到大排序（这个地方没有采用极角逆序排序，所以要进行两次扫描），删除重复的点后得到的序列p1,p2.....,然后把p1和p2放到凸包中。从p3开始，当新的

点在凸包“前进”方向的左边时继续，否则依次删除最近加入凸包的点，直到新点在左边；**/

//Goal[]数组模拟栈的使用；

int ConvexHull(Point* P,int n,Point* Goal){

    sort(P,P+n);

    int m = unique(P,P+n) - P;    //对点进行去重；

    int cnt = ;

    for(int i=;i<m;i++){       //求下凸包；

        while(cnt> && dcmp(Cross(Goal[cnt-]-Goal[cnt-],P[i]-Goal[cnt-])) <= )  cnt--;

        Goal[cnt++] = P[i];

    }

    int temp = cnt;

    for(int i=m-;i>=;i--){     //逆序求上凸包；

        while(cnt>temp && dcmp(Cross(Goal[cnt-]-Goal[cnt-],P[i]-Goal[cnt-])) <= ) cnt--;

        Goal[cnt++] = P[i];

    }

    if(cnt > ) cnt--;  //减一为了去掉首尾重复的；

    return cnt;

}

/*********************************分割线******************************/

Point P[maxn*],Goal[maxn*];

int n;

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    while(T--){

        cin>>n;

        int cnt = ;

        double x,y,w;

        for(int i=;i<=n;i++){

            scanf("%lf %lf %lf",&x,&y,&w);

            P[cnt++] = Point(x,y);

            P[cnt++] = Point(x+w,y);

            P[cnt++] = Point(x,y+w);

            P[cnt++] = Point(x+w,y+w);

        }

        cnt = ConvexHull(P,cnt,Goal);

        double Maxlen = ;

        for(int i=;i<cnt;i++)

           for(int j=i+;j<cnt;j++){

             Maxlen = max(Maxlen,Length(Goal[j]-Goal[i]));

        }

        printf("%.lf\n",Maxlen);

    }

    return ;

}

旋转卡壳：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = ;

const int maxe = ;

const int INF = 0x3f3f3f;

const double eps = 1e-;

const double PI = acos(-1.0);

struct Point{

    double x,y;

    Point(double x=, double y=) : x(x),y(y){ }    //构造函数

};

typedef Point Vector;

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

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

Vector operator * (Vector A , double p){return Vector(A.x*p,A.y*p);}

Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){

    return a.x < b.x ||( a.x == b.x && a.y < b.y);

}

int dcmp(double x){

    if(fabs(x) < eps) return ;

    else              return x <  ? - : ;

}

bool operator == (const Point& a, const Point& b){

    return dcmp(a.x - b.x) ==  && dcmp(a.y - b.y) == ;

}

///向量（x,y）的极角用atan2(y,x);

double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }

double Length(Vector A)    { return Dot(A,A); }

double Angle(Vector A, Vector B)  { return acos(Dot(A,B) / Length(A) / Length(B)); }

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

//凸包：

/**Andrew算法思路：首先按照先x后y从小到大排序（这个地方没有采用极角逆序排序，所以要进行两次扫描），删除重复的点后得到的序列p1,p2.....,然后把p1和p2放到凸包中。从p3开始，当新的

点在凸包“前进”方向的左边时继续，否则依次删除最近加入凸包的点，直到新点在左边；**/

// 如果不希望在凸包的边上有输入点，把两个 <= 改成 <

//Goal[]数组模拟栈的使用；

int ConvexHull(Point* P,int n,Point* Goal){

    sort(P,P+n);

    int m = unique(P,P+n) - P;    //对点进行去重；

    int cnt = ;

    for(int i=;i<m;i++){       //求下凸包；

        while(cnt> && dcmp(Cross(Goal[cnt-]-Goal[cnt-],P[i]-Goal[cnt-])) <= )  cnt--;

        Goal[cnt++] = P[i];

    }

    int temp = cnt;

    for(int i=m-;i>=;i--){     //逆序求上凸包；

        while(cnt>temp && dcmp(Cross(Goal[cnt-]-Goal[cnt-],P[i]-Goal[cnt-])) <= ) cnt--;

        Goal[cnt++] = P[i];

    }

    if(cnt > ) cnt--;  //减一为了去掉首尾重复的；

    return cnt;

}

//旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离

//计算凸包直径，输入凸包Goal，顶点个数为n，按逆时针排列，输出直径的平方

double RotatingCalipers(Point* Goal,int n){

    double ret = ;

    Goal[n]=Goal[];  //补上使凸包成环；

    int pv = ;

    for(int i=;i<n;i++){   //枚举边Goal[i]Goal[i+1],与最远顶点Goal[pv];利用叉积求面积的方法求最大直径；；

        while(fabs(Cross(Goal[i+]-Goal[pv+],Goal[i]-Goal[pv+]))>fabs(Cross(Goal[i+]-Goal[pv],Goal[i]-Goal[pv])))

              pv = (pv+)%n;

        ret=max(ret,max(Length(Goal[i]-Goal[pv]),Length(Goal[i+]-Goal[pv+]))); //这个地方不太好理解，就是要考虑当pv与pv+1所在直线平行于i与i+1的情况；

    }

    return ret;

}

/*********************************分割线******************************/

Point P[maxn*],Goal[maxn*];

int n;

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    while(T--){

        cin>>n;

        int cnt = ;

        double x,y,w;

        for(int i=;i<=n;i++){

            scanf("%lf %lf %lf",&x,&y,&w);

            P[cnt++] = Point(x,y);

            P[cnt++] = Point(x+w,y);

            P[cnt++] = Point(x,y+w);

            P[cnt++] = Point(x+w,y+w);

        }

        cnt = ConvexHull(P,cnt,Goal);

        double Maxlen = RotatingCalipers(Goal,cnt);

        printf("%.lf\n",Maxlen);

    }

    return ;

}