2016-08-29

HDU 5733 tetrahedron【几何公式】

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5733

题意：

给定四个点，判断能否组成四面体，若能求内切球半径和坐标。

分析：

判断能否组成四面体：求出其中三点构成的平面，判断另一个点是否在平面上。
求内切球半径和坐标：利用海伦公式$S = \sqrt{s1 (s1-a) (s1-b)*(s1-c)}$，其中$s1$表示的是三角形的周长的一半。
最后求内切球的球心：

设四面体$A_1A_2A_3A_4$的顶点$A_i$所对的侧面面积为$S_i(i=1,2,3,4)$，顶点$A_i$坐标为$(x_i, y_i, z_i)(i=1,2,3,4)$，内心坐标为$(x_0,y_0, z_0)$，则有
$x_0=( S_1x_1+S_2x_2 +S_3x_3+S_4x_4)/(S_1+S_2+S_3+S_4);$
$y_0=( S_1y_1+S_2y_2 +S_3y_3+S_4y_4)/(S_1+S_2+S_3+S_4);$
$z_0=( S_1z_1+S_2z_2 +S_3z_3+S_4z_4)/(S_1+S_2+S_3+S_4);$

最后利用点到平面的距离，求出半径。

代码：

/*************************************************************************
    > File Name: 5733.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/26 21:13:36
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 4 + 5;
double eps = 1e-8;
struct Point{
	double x, y, z;
}p[maxn];
double S[maxn], a[maxn][maxn];
double A, B, C, D;
bool judge(Point p1, Point p2, Point p3, Point p4)  
{  
	A = (p2.y - p1.y) * (p3.z - p1.z) - (p2.z - p1.z) * (p3.y - p1.y);  
    B = (p2.z - p1.z) * (p3.x - p1.x) - (p2.x - p1.x) * (p3.z - p1.z);  
    C = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);  
	D = 0- (A * p1.x + B * p1.y + C * p1.z);
    return fabs(A * (p4.x - p1.x) + B * (p4.y - p1.y) + C * (p4.z - p1.z)) < eps;
}  
int main (void)
{
	while(~scanf("%lf%lf%lf", &p[0].x, &p[0].y, &p[0].z)){
		for(int i = 1; i < 4; i++) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
		if(judge(p[0], p[1], p[2], p[3])){
			puts("O O O O");
			continue;
		}
		for(int i = 0; i < 4; i++){
			for(int j = i + 1; j < 4; j++){
				a[i][j] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y) + (p[i].z - p[j].z) * (p[i].z - p[j].z));
			}
		}
		double s1 = a[1][2] + a[2][3] + a[1][3]; s1 /= 2.0;
		S[0] = sqrt(s1 * (s1 - a[1][2]) * (s1 - a[2][3]) * (s1 - a[1][3]));
		double s2 = a[0][2] + a[0][3] + a[2][3]; s2 /= 2.0;
		S[1] = sqrt(s2 * (s2 - a[0][2]) * (s2 - a[0][3]) * (s2 - a[2][3]));
		double s3 = a[0][1] + a[0][3] + a[1][3]; s3 /= 2.0;
		S[2] = sqrt(s3 * (s3 - a[0][1]) * (s3 - a[1][3]) * (s3 - a[0][3]));
		double s4 = a[0][2] + a[0][1] + a[1][2]; s4 /= 2.0;
		S[3] = sqrt(s4 * (s4 - a[0][2]) * (s4 - a[0][1]) * (s4 - a[1][2]));
		double totS = 0, totx = 0, toty = 0, totz = 0;
		for(int i = 0; i < 4; i++){
			totx += S[i] * p[i].x;
			toty += S[i] * p[i].y;
			totz += S[i] * p[i].z;
			totS += S[i];
		}
		totx /= totS, toty /= totS, totz /= totS;
		double r = fabs(A * totx + B * toty + C * totz + D) / sqrt(A * A + B * B + C * C);
		printf("%.4f %.4f %.4f %.4f\n", totx, toty, totz, r);
	}
	return 0;
}