分治法解凸包面积code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, x[N], y[N];
int mx, mn, sumS;
bool vis[N];

int S(int p1, int p2, int p3){
	return ((x[p2] - x[p1])*(y[p3] - y[p2]) - (x[p3] - x[p2])*(y[p2] - y[p1]));
}

void RS(int l, int r){
	int maxS=-1, p=0;
	for(int i=1; i<=n; ++i){
		int temp=S(l,r,i);
		if(!vis[i] && temp<0){
			temp*=-1;
			if(temp>maxS) p=i, maxS=temp;
		}
	}
	if(p==0) return ;
	vis[p]=1;
	sumS+=maxS;
	RS(l,p);
	RS(p,r);

}

void LS(int l, int r){
	int maxS=-1, p=0;
	for(int i=1; i<=n; ++i){
		int temp=S(l,r,i);
		if(!vis[i] && temp>0){
			if(temp>maxS) p=i, maxS=temp;
		}
	}
	if(p==0) return ;
	vis[p]=1;
	sumS+=maxS;
	LS(l,p);
	LS(p,r);
}

void solve(){
	memset(vis,0,sizeof(vis));
	sumS=0;
	mx=mn=1;

	cin>>n;
	cin>>x[1]>>y[1];
	for(int i=2; i<=n; i++){
		cin>>x[i]>>y[i];
		if(x[i]>x[mx]) mx=i;
		if(x[i]<x[mn]) mn=i;
	}
	vis[mn]=vis[mx]=1;
	LS(mn, mx);
	RS(mn, mx);
	printf("%.1lf\n", sumS/2.0);
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

最近对的分治解法code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline double mymin(double x,double y){return x<y?x:y;}
struct node
{
    int x, y;
}a[N];
int n;
int xd[N], k;
bool cmp(node a, node b){
    return a.x<b.x;
}
bool cmp2(int p1, int p2){
    return a[p1].y < a[p2].y;
}
double dis(node p1, node p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

double fun(int l, int r){
    if(l==r) return INF;
    if(l+1==r) return dis(a[l],a[r]);
    int mid=(l+r)>>1;
    double ans=mymin(fun(l,mid), fun(mid+1,r));
    k=0;
    for(int i=l; i<=r; ++i)
        if(fabs(a[mid].x - a[i].x) <= ans)
            xd[++k]=i;
    sort(xd+1,xd+1+k,cmp2);
    for(int i=1; i<=k; ++i){
        int temp=i+7>k ? k:i+7;
        for(int j=i+1; j<=temp; ++j){
            if(a[xd[j]].y - a[xd[i]].y >= ans) break;
            ans=mymin(ans,dis(a[xd[i]], a[xd[j]]));
        }
    }
    return ans;
}

void solve(){
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n,cmp);
    printf("%.4lf\n", fun(1,n));
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}