Graham's Scan法
求解凸包问题。
我写的是按照逆时针扫描，其中叉乘函数返回的是
的结果。凸包的结果保存在栈S[0...top]中。
的结果。凸包的结果保存在栈S[0...top]中。PS:
1、求凸包时，必须确定至少有3个点。
2、一般把极点 S[0] 在最后 S[top+1] 处复制一份，便于计算。
3、初始化放2个点即可，3个点可能有bug（考虑开始三个点即 P[0]、P[1]、P[2] 共线的情况）。
4、排序时，对于极角相同的点，把距离小的排在前面比较好。这样求凸包时，可以把共线的点全部删掉，只保留距离最大的那个点。
否则，求凸包时，程序会把这些共线的点全部加入凸包，使凸包上的点增加。（小优化）
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1005
struct Point
{
int x,y;
}P[N],S[N];
int n,top;
double Dis(const Point& p1,const Point& p2)
{
return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)*1.0 );
}
double Cross(const Point& p1,const Point& p2,const Point& p3,const Point& p4)
{
return (p2.x-p1.x)*(p4.y-p3.y) - (p2.y-p1.y)*(p4.x-p3.x);
}
bool cmp(const Point& p1,const Point& p2)
{
double C = Cross(P[0],p1,P[0],p2);
return C ? C>0 : Dis(P[0],p1)<Dis(P[0],p2);
}
void Pole_Point()
{
int id;
Point pp = P[id=0];
for(int i=1;i<n;i++)
if(P[i].y < pp.y || P[i].y == pp.y && P[i].x < pp.x)
pp = P[i] , id = i;
P[id] = P[0] , P[0] = pp;
}
void Convex_Hull()
{
Pole_Point();
sort(P+1,P+n,cmp);
S[0]=P[0],S[top=1]=P[1];
for(int i=2;i<n;i++)
{
while(top && Cross(S[top-1],S[top],S[top],P[i]) <= 0)
--top;
S[++top] = P[i];
}
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
scanf("%d%d",&P[i].x,&P[i].y);
Convex_Hull();
for(int i=0;i<=top;i++)
printf("%d %d\n",S[i].x,S[i].y);
}
return 0;
}