一、分治法
找到横坐标最小和最大的两个点p0和p1，它们一定在凸包上(横坐标最小、最大的若多个点，随意取一个即可)，然后在直线p0p1的其中一边找离直线最远的一个点，它也一定在凸包上，以后每次向外部(内部的点一定不是凸包上的点)找离现有直线最远的一个点；再在直线p0p1的另一边进行同样的操作
实现细节：一开始将点用x、y坐标进行双关键字排序，事实上每次找到一个点之后，相当于把原(矩形)空间分成了两个子(矩形)空间，距离直接用三角形有向面积判断即可，有向面积判断还能顺便判断是在内部还是外部
时间复杂度事实上和快排一样取决于数据分布，一般认为是O(nlogn)
二、Jarvis步进法
找到纵坐标最小的点作为起点，每次找极角最小(相等则取最远)的点作为凸包下一个点
时间复杂度O(hn)，h为凸包上点数
三、Graham扫描法
找到纵坐标最小的点作为起点，以该点为极点进行极角排序，用一个栈维护前进方向
时间复杂度O(nlogn)
四、Andrew算法(推荐使用)
以x、y进行双关键字排序，找到横坐标最小的点，然后用一个栈维护前进方向，求一个下凸包再求一个上凸包
时间复杂度O(nlogn)
hdu1392 一道裸凸包题，但数据有点奇怪，n=2时要特判
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;#define rep(i,a,b) for(int i=a;i<=b;++i) #define arcrep(i,a,b) for(int i=a;i>=b;--i)const int MAXN=200000+10;struct point{long long x,y;point(){}point (long long a,long long b): x(a),y(b) {}friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}friend point operator * (const long long &r,const point &a){return point(r*a.x,r*a.y);}friend bool operator == (const point &a,const point &b){return a.x==b.x && a.y==b.y;}double norm(){return sqrt(x*x+y*y);} };inline long long det(point a,point b) {return a.x*b.y-a.y*b.x;} inline long long dot(point a,point b) {return a.x*b.x+a.y*b.y;} inline double dist(point a,point b) {return (a-b).norm();}point ori[MAXN+10],con[MAXN+10];bool cmp(const point &a,const point &b) {return (a.x<b.x || (a.x==b.x && a.y<b.y)); }//Graham算法 input:ori数组 output:con数组 int Graham(int n) {sort(ori+1,ori+n+1,cmp); //排序后第1和第n个点必定属于凸包int temp=0;rep(i,1,n){while (temp>=2 && det(con[temp]-con[temp-1],ori[i]-con[temp])<=0) --temp;con[++temp]=ori[i];}int ans=temp;arcrep(i,n-1,1){while (ans>temp && det(con[ans]-con[ans-1],ori[i]-con[ans])<=0) --ans;con[++ans]=ori[i];}if (n>1) --ans;return ans; }int n,num;
double ans;
int main() {while (~scanf("%d",&n)){if (n==0) break;rep(i,1,n) scanf("%lld%lld",&ori[i].x,&ori[i].y);if (n==2) {printf("%.2f\n",dist(ori[1],ori[2]));continue;}num=Graham(n);ans=0;rep(i,1,num-1) ans+=dist(con[i],con[i+1]);ans+=dist(con[num],con[1]);printf("%.2f\n",ans);}return 0; }
旋转卡壳的核心思路是寻找对踵点
旋转卡壳裸题poj2187(可直接用int或者long long)
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;#define rep(i,a,b) for(int i=a;i<=b;++i) #define arcrep(i,a,b) for(int i=a;i>=b;--i)const int MAXN=200000+10; struct point{int x,y;point(){}point (int a,int b): x(a),y(b) {}friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}friend point operator * (const int &r,const point &a){return point(r*a.x,r*a.y);}friend bool operator == (const point &a,const point &b){return a.x==b.x && a.y==b.y;}int sqrnorm(){return x*x+y*y;} };inline int det(point a,point b) {return a.x*b.y-a.y*b.x;} inline int dot(point a,point b) {return a.x*b.x+a.y*b.y;} inline int sqrdist(point a,point b) {return (a-b).sqrnorm();}point ori[MAXN+10],con[MAXN+10];bool cmp(const point &a,const point &b) {return (a.x<b.x || (a.x==b.x && a.y<b.y)); }//Graham算法 input:ori数组 output:con数组 int Graham(int n) {sort(ori+1,ori+n+1,cmp); //排序后第1和第n个点必定属于凸包int temp=0;rep(i,1,n){while (temp>=2 && det(con[temp]-con[temp-1],ori[i]-con[temp])<=0) --temp;con[++temp]=ori[i];}int ans=temp;arcrep(i,n-1,1){while (ans>temp && det(con[ans]-con[ans-1],ori[i]-con[ans])<=0) --ans;con[++ans]=ori[i];}if (n>1) --ans;return ans; }int mindist(int m) {int ans=0;int temp;con[m+1]=con[1];int j=2;for (int i=1;i<=m;++i){while (abs(det(con[j]-con[i],con[i+1]-con[i]))<abs(det(con[j+1]-con[i],con[i+1]-con[i]))){++j;if (j>m) j=1;}temp=sqrdist(con[i],con[j]);if (temp>ans)ans=temp;}return ans; }int n,m; int ans;int main() {scanf("%d",&n);rep(i,1,n) scanf("%d%d",&ori[i].x,&ori[i].y);m=Graham(n);ans=mindist(m);printf("%d\n",ans);return 0; }
