凸包面积算法

1.选取p0作为y坐标最小的点，如果y坐标相等，选取x坐标最小的点

2.对剩余的点相对与p0点的极角进行排序(比较叉积)

3.去除极角相等的点，即距离最远的点

4.初始化堆栈

5.折线段拐向判断，若没有左转的时候出栈点，否则入栈

6.根据已有的点计算面积

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int x[110],y[110],used[110]={0};
double size;
double TriangleSize(int i,int j,int k){
    int x1=x[i],x2=x[j],x3=x[k],y1=y[i],y2=y[j],y3=y[k];
    used[i]=used[j]=used[k]=1;
    return 0.5*fabs((double)(x2-x1)*(y3-y2)-(y2-y1)*(x3-x2));
}
double calArea(int i,int j,int k){
        int x1=x[i],x2=x[j],x3=x[k],y1=y[i],y2=y[j],y3=y[k];
        return 0.5*((x2-x1)*(y3-y2)-(y2-y1)*(x3-x2));
}
void calLsize(int n,int p1,int p2){
    int p=-1;
    double sizeMax=-1;
    for(int i=0;i<n;i++){
        if(used[i]==1||calArea(p1,p2,i)<=0||i==p1||i==p2) continue;
        if(calArea(p1,p2,i)>sizeMax)
        {
            sizeMax=calArea(p1,p2,i);
            p=i;
         } 
    }
    if(p==-1) return;
    size +=TriangleSize(p1,p2,p);
    calLsize(n,p1,p);
    calLsize(n,p,p2);
}
void calRsize(int n,int p1,int p2){
    int p=-1;
    double sizeMax=-1;
    for(int i=0;i<n;i++){
    if(used[i]==1||calArea(p1,p2,i)>=0||i==p1||i==p2) continue;
        if(-calArea(p1,p2,i)>sizeMax)
        {
            sizeMax=-calArea(p1,p2,i);
            p=i;
         } 
    }
    if(p==-1) return;
    size +=TriangleSize(p1,p2,p);
    calRsize(n,p1,p);
    calRsize(n,p,p2);
}
void calSize(int n,int p1,int p2){
    calLsize(n,p1,p2);
    calRsize(n,p1,p2);
}
int main(){
    int t,n,i,j,maxX,minX;
    cin>>t;
    for(i=0;i<t;i++){
        size=0;
        cin>>n;
        for(j=0;j<n;j++){
            cin>>x[j]>>y[j];
            used[j]=0;
        }
        maxX=minX=0;
        for(j=0;j<n;j++){
            if(x[j]>x[maxX]) maxX=j;
            if(x[j]<x[minX]) minX=j;
        }
        calSize(n,minX,maxX);
        printf("%.1lf\n",size);
    }
    return 0;
}