分治法解凸包面积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;
}
Comments | NOTHING