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);$

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*************************************************************************
> 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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: