凸包就是给你一堆点,再给你一根绳子你用这个绳子把这堆点围起来!绳子与这些点所接触的点叫做凸包点,围成的图形叫做凸包!
具体讲解看这里here
下面是我个人的板子,做了好多题的磨练证明我的板子是可以带出门的
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,tot;///n为二维平面上点的个数,tot为凸包上点的个数
struct Point
{
int x,y;
Point(double x=0,double y=0):x(x),y(y){}
}a[10009],p[10009];///p[]用来储存凸包
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double dis(Point a,Point b)///距离此处没有进行开平方!!!!!!!!!
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double Wai(Point p0,Point p1,Point p2) ///判断向量p2是否在p0,p1的左边是返回正值其他相反
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int cmp(Point p1,Point p2)///极角排序;
{
int x=Wai(p1,p2,a[0]);
if(x>0||(x==0&&dis(p1,a[0])<dis(p2,a[0]))) return 1;
return 0;
}
void Graham()
{
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);
tot=2,p[0]=a[0],p[1]=a[1];
for(int i=2;i<n;i++)
{
while(tot>1&&Wai(p[tot-1],p[tot-2],a[i])>=0) tot--;
p[tot++]=a[i];
}
}
double c()///输出周长
{
double dist=0;
for(int i=0;i<tot-1;i++)
{
dist+=sqrt(dis(p[i],p[i+1]));
}
dist+=sqrt(dis(p[tot-1],p[0]));
return dist;
}
double s()///输出面积
{
double ss=0;
for(int i=1;i<tot-1;i++)
{
ss+=(Wai(p[0],p[i],p[i+1])/2);
}
return ss;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
Graham();
for(int i=0;i<tot;i++)
cout<<p[i].x<<" "<<p[i].y<<endl;
return 0;
}
/*
5
0 0
2 0
2 1
1 1
0 1
*/