向量的叉乘就是由该两个向量所组成的平行四边形的面积(x1y2-x2y1).
这个凸包不是太懂.先留模板在此
这个是水平排序
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int MAX = 1e3+7;
//const int maxn = 3e6+5;
const int mod = 1000000007;
const db eps = 1e-7;
int ca = 1;
struct PO
{
int x, y;
PO (){};
PO (int x, int y):x(x), y(y){};
friend PO operator - (const PO&a, const PO&b)
{
return PO(a.x-b.x, a.y-b.y);
}
};
PO pos[MAX];//存点
PO ch[MAX];//栈
bool cmp(const PO&a, const PO&b)
{
if(a.x==b.x)return a.y<b.y;
else return a.x<b.x;
}
int cross(const PO&a, const PO&b)
{
return a.x*b.y-a.y*b.x;
}
int n;
void solve()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d%d", &pos[i].x, &pos[i].y);
sort(pos, pos+n, cmp);
//第一条链
int m = 0;
for(int i=0; i<n; i++)
{
while(m>1 && cross(pos[i]-ch[m-2], ch[m-1]-ch[m-2])>=0) m--;
ch[m++] = pos[i];
}
//第二条链
int temp = m;
for(int i=n-2; i>=0; i--)
{
while(m>temp && cross(pos[i]-ch[m-2], ch[m-1]-ch[m-2])>=0) m--;
ch[m++] = pos[i];
}
if(n>1) m--;
cout << "______________"<<endl;
for(int i=0; i<m; i++)
printf("%d %d\n", ch[i].x, ch[i].y);
}
int main()
{
//Frei
//Freo
int t = 1;
//cin >> t;
while (t--) solve();
}
这个是极角排序
#include<stdio.h>
#include<math.h>
#define eps 1e-10
#define pi 3.1415926535898
#define N 1010
/*
point[]：输入的点集
ch[]：输出的凸包上的点集，按照逆时针方向排列
n：point中的点的数目
len：输出的凸包上的点的个数
*/
struct node
{
double x,y;
} point[N],ch[N];
int n,len;
double multi(node a,node b,node c)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void graham_scan(node point[N],node ch[N],int n)
{
int i,j,k,top;
struct node t;
k=0; //找到最下且偏左的那个点
for(i=1; i<n; i++)
if(point[i].y<point[k].y||(point[i].y==point[k].y&&(point[i].x<point[k].x)))
k=i;
t=point[0];//将这个点指定为point[0];
point[0]=point[k];
point[k]=t;
//按极角从小到大,距离偏短进行排序
for(i=1; i<n-1; i++)
{
k=i;
for(j=i+1; j<n; j++)
if(multi(point[j],point[k],point[0])>0||(fabs(multi(point[j],point[k],point[0]))<=eps&&
(dis(point[0],point[j])<dis(point[0],point[k]))))
k=j; //k保存极角最小的那个点,或者相同距离原点最近
t=point[i];
point[i]=point[k];
point[k]=t;
}
//第三个点先入栈
ch[0]=point[0];
ch[1]=point[1];
ch[2]=point[2];
top=2; //判断与其余所有点的关系
for(i=3; i<n; i++)
{
//不满足向左转的关系,栈顶元素出栈
while(multi(point[i],ch[top],ch[top-1])>0||fabs(multi(point[i],ch[top],ch[top-1]))<=eps)
top--;
//当前点与栈内所有点满足向左关系,因此入栈
ch[++top]=point[i];
}
len=top+1;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
graham_scan(point,ch,n);
for(i=0; i<len; i++)
printf("%lf %lf\n",ch[i].x,ch[i].y);
}
return 0;
}
