[BZOJ1964]hull 三维凸包：计算几何

分析

发现自己并不会计算几何。

所以先引用一下这位dalao的博客。

二维平面四个点求凸包面积->任选三个点面积之和/2

三维平面五个点求凸包体积->任选四个点体积之和/2

二维平面三个点面积->二个二维向量行列式值的绝对值/2

三维平面四个点体积->三个三维向量行列式值的绝对值/6

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

struct Vector{

	LL x,y,z;

	friend Vector operator - (Vector x,Vector y){

		return (Vector){x.x-y.x,x.y-y.y,x.z-y.z};

	}

}a[6];

double ans;

inline double solve(Vector v1,Vector v2,Vector v3){

	return fabs(1.0*v1.x*v2.y*v3.z

		-v1.x*v2.z*v3.y

		+v1.y*v2.z*v3.x

		-v1.y*v2.x*v3.z

		+v1.z*v2.x*v3.y

		-v1.z*v2.y*v3.x)/6;

}

int main(){

	rin(i,1,5) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);

	rin(i,1,2) rin(j,i+1,3) rin(k,j+1,4) rin(l,k+1,5)

		ans+=solve(a[i]-a[l],a[j]-a[l],a[k]-a[l]);

	ans/=2.0;

	printf("%.2lf\n",ans);

	return 0;

}

巴特西

[BZOJ1964]hull 三维凸包：计算几何

分析

代码

最新文章

热门文章