凸包入门
什么是凸包？
假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图：
然后，什么是凸包问题？
我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。
现给出点的数目13，和各个点的坐标。求构成凸包的点？
自己才刚刚接触到这个数学问题。通过几个入门的简单的题，基本上已经有了简单的了解。所以自己先写点东西。为了自己以后
可以好好的复习。
其实凸包就是凸多边形问题。
大佬的博客：凸包五解
1 凸包问题要求什么？
一般的话来说，入门就是要你找出这个凸多边型，求凸多边的型的面积，周长。其实写到这就可以思考一下，如何求多边。只要
把多边形求出来，那么相对来说就是可以找到周长，面积了。
2: 如何求?
其实大佬的博客中，将这个思想已经完全的讲解出来了。
(1)点的输入
(2)找出很明显的凸包上点的，作为一个开头。
(3)极角排序。
int dis(node c1,node c2)
{
return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
}
double mutil(node c0,node c1,node c2)
{
return (c1.x-c0.x)*(c2.y-c0.y)-(c2.x-c0.x)*(c1.y-c0.y);
}
int cmp(node c1,node c2)
{
int x=mutil(c1,c2,a[0]);
if(x>0||(x==0&&dis(c1,a[0])<dis(c2,a[0])))
return 1;
else
return 0;
}
(4)开始扫描，利用叉乘来判断是不是凸包上的点，将凸包上的点收入到栈堆中（数组也可以）
void Graham()
{
tot=2;
p[0]=a[0],p[1]=a[1];
for(int i=2; i<n; i++)
{
while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0)
tot--;
p[tot++]=a[i];
}
}
俩个简单的题
NYOJ-78 圈水池 入门凸包输出点
int n,tot;
struct node
{
int x,y;
} a[10005],p[10005];
int dis(node c1,node c2)
{
return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
}
double mutil(node c0,node c1,node c2)
{
return (c1.x-c0.x)*(c2.y-c0.y)-(c2.x-c0.x)*(c1.y-c0.y);
}
int cmp(node c1,node c2)
{
int x=mutil(c1,c2,a[0]);
if(x>0||(x==0&&dis(c1,a[0])<dis(c2,a[0])))
return 1;
else
return 0;
}
int cmp1(node a,node b)
{
if(a.x==b.x)
return a.y<b.y;
else
return a.x<b.x;
}
void Graham()
{
tot=2;
p[0]=a[0],p[1]=a[1];
for(int i=2; i<n; i++)
{
while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0)
tot--;
p[tot++]=a[i];
}
sort(p,p+tot,cmp1);
for(int i=0;i<tot;i++)
printf("%d %d\n",p[i].x,p[i].y);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
int k=0;
for(int i=0; i<n; i++)
{
if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))
k=i;
}
swap(a[0],a[k]);
sort(a+1,a+n,cmp);
// for(int i=0; i<n; i++)
// {
// printf("******%d %d\n",a[i].x,a[i].y);
// }
Graham();
}
}
POJ-3348 Cows 入门求面积
void Graham()
{
tot=2;
p[0]=a[0],p[1]=a[1];
for(int i=2; i<n; i++)
{
while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0)
tot--;
p[tot++]=a[i];
}
int sum=0;
for(int i=2; i<tot; i++)
{
int l=(int)mutil(p[0],p[i-1],p[i]); //在求面积的时候就可以直接用向量来求。即平行四边的面积
就等于两条边的乘积除以2；
sum+=abs(l)/2;
}
printf("%d",sum/50);
}