凸包

向量的叉乘就是由该两个向量所组成的平行四边形的面积(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;
}