HDOJ 5733 tetrahedron

题目链接：HDOJ5733

2016第一场多校的一个计算几何模板题

题意：给定四个点的坐标，如果是四面体的话，求出内切球的球心坐标和球径

kuangbin模板+百度公式

先说说如何判断是不是四面体

四点不共面+任意三点不共线：四个点构成四面体

公式：在代码里有

计算几何不需要解释太多，无非就是模板中的点乘叉乘搞几下，画个图就能够出来

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-8;
const int MAXN=550;
int sgn(double x){
	if (fabs(x)<eps) return 0;
	if (x<0) return -1;
	return 1;
}

struct Point3{
	double x,y,z;
	Point3(double _x=0,double _y=0,double _z=0){
		x=_x,y=_y,z=_z;
	}
	void input(){
		scanf("%lf%lf%lf",&x,&y,&z);
	}
	bool operator == (const Point3 &b) const{
		return sgn(x-b.x)==0 && sgn(y-b.y)==0 &&sgn(z-b.z)==0;
	}
	double len(){
		return sqrt(x*x+y*y+z*z);
	}
	double len2(){
		return x*x+y*y+z*z;
	}
	double distance(const Point3 &b) const{
		return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
	}
	Point3 operator - (const Point3 &b) const{
		return Point3(x-b.x,y-b.y,z-b.z);
	}
	Point3 operator + (const Point3 &b) const{
		return Point3(x+b.x,y+b.y,z+b.z);
	}
	Point3 operator * (const double &k) const{
		return Point3(x*k,y*k,z*k);
	}
	Point3 operator / (const double &k) const{
		return Point3(x/k,y/k,z/k);
	}
	double operator * (const Point3 &b) const{
		return x*b.x+y*b.y+z*b.z;
	}
	Point3 operator ^ (const Point3 &b) const{
		return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
	}
};

//叉乘就是求出了法向量 
Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c){
	return (b-a)^(c-a);
}

//求三角形的面积公式（空间内三点）
double area(Point3 a,Point3 b,Point3 c){
	return ((b-a)^(c-a)).len()/2.0;
}

//求四面体的面积公式（空间内不共面，且任意三点不共闲的四点）
double volume(Point3 a,Point3 b,Point3 c,Point3 d){
	return ((b-a)^(c-a))*(d-a)/6.0;
}

//判断四点是否共面
int dots_onplane(Point3 a,Point3 b,Point3 c,Point3 d){
	return sgn(cross(a,b,c)*(d-a))==0;
}

//判断三点是否共线
int dots_inline(Point3 a,Point3 b,Point3 c){
	return ((a-b)^(b-c)).len()<eps;
}

Point3 A,B,C,D;

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%lf%lf%lf",&A.x,&A.y,&A.z)!=EOF){
		B.input();C.input();D.input();
		if (dots_onplane(A,B,C,D)||dots_inline(A,B,C)||
			dots_inline(A,B,D)||dots_inline(A,C,D)||dots_inline(B,C,D)){
				puts("O O O O");
				continue;
			}
		double s1=area(B,C,D);
		double s2=area(A,C,D);
		double s3=area(A,B,D);
		double s4=area(A,B,C);
		double R=3.0*volume(A,B,C,D)/(s1+s2+s3+s4);
		double x1=(s1*A.x+s2*B.x+s3*C.x+s4*D.x)/(s1+s2+s3+s4);
		double y1=(s1*A.y+s2*B.y+s3*C.y+s4*D.y)/(s1+s2+s3+s4);
		double z1=(s1*A.z+s2*B.z+s3*C.z+s4*D.z)/(s1+s2+s3+s4);
		printf("%.4lf %.4lf %.4lf %.4lf\n",x1,y1,z1,fabs(R));
	}
	return 0;
}