luogu P4724 模板三维凸包

LINK：三维凸包

一个非常古老的知识点。估计也没啥用。

大体上了解了过程能背下来就背下来吧.

一个bf：暴力枚举三个点此时只需要判断所有的点都在这个面的另外一侧就可以说明这个面是三维凸包上的面了。

一个问题：多点共面问题。一个trick：可以利用扰动法然后就可以解决这个问题了。

正解：(n^2)的增量法求三维凸包。

先加入三个不共线的点组成一个面(正反两面然后不断加入点。

然后考虑每一个点删除这个点可以看到的面然后边界与新加入的点连边即可。

具体理解看代码(我也有点迷。。

code

//#include<bitsstdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define vep(p,n,i) for(RE int i=p;i<n;++i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 1000000007
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define EPS 1e-9
#define sq sqrt
#define mod 998244353
#define S second
#define F first
#define op(x) t[x].op
#define d(x) t[x].d
#define Set(a,v) memset(a,v,sizeof(a))
#define pf(x) ((x)*(x))
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    RE int x=0,f=1;RE char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=2010;
int n,cnt;
int vis[MAXN][MAXN];
db ans=0;
db Rand(){return rand()/(db)RAND_MAX;}
db reps() {return (Rand()-0.5)*EPS;}
struct Vec
{
	db x,y,z;
	void shake(){x+=reps();y+=reps();z+=reps();}//扰动.
	db len(){return sq(pf(x)+pf(y)+pf(z));}
	Vec operator -(Vec a){return (Vec){x-a.x,y-a.y,z-a.z};}
	Vec operator %(Vec a){return (Vec){y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x};}
	db operator *(Vec a){return x*a.x+y*a.y+z*a.z;}
}a[MAXN];
typedef Vec point;
struct wy
{
	int v[3];
	Vec Nor(){return (a[v[1]]-a[v[0]])%(a[v[2]]-a[v[0]]);}
	db area(){return Nor().len()/2.0;}
}f[MAXN],c[MAXN];
inline bool pd(wy c,Vec b){return ((b-a[c.v[0]])*c.Nor())>0;}
inline void Convex_3D()
{
	f[cnt=1].v[0]=1;
	f[cnt=1].v[1]=2;
	f[cnt=1].v[2]=3;
	f[cnt=2].v[0]=3;
	f[cnt=2].v[1]=2;
	f[cnt=2].v[2]=1;
	rep(4,n,i)
	{
		int cc=0;
		rep(1,cnt,j)
		{
			int ww=pd(f[j],a[i]);
			if(!ww)c[++cc]=f[j];
			rep(0,2,k)vis[f[j].v[k]][f[j].v[(k+1)%3]]=ww;
		}
		rep(1,cnt,j)
		{
			rep(0,2,k)
			{
				int x=f[j].v[k],y=f[j].v[(k+1)%3];
				if(vis[x][y]&&!vis[y][x])
				{
					c[++cc].v[0]=x;c[cc].v[1]=y;c[cc].v[2]=i;
				}
			}
		}
		rep(1,cc,j)f[j]=c[j];
		cnt=cc;
	}
}
int main()
{
	freopen("1.in","r",stdin);
	gt(n);rep(1,n,i)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z),a[i].shake();
	Convex_3D();rep(1,cnt,i)ans+=f[i].area();
	printf("%.3lf",ans);return 0;
}

luogu P4724 模板 三维凸包

luogu P4724 模板三维凸包