HDU5840 Special Tetrahedron 暴力计算几何

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

Special Tetrahedro

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Given n points which are in three-dimensional space(without repetition).

Please find out how many distinct Special Tetrahedron among them. A tetrahedron is called Special Tetrahedron if it has two following characters.

1. At least four edges have the same length.

2. If it has exactly four edges of the same length, the other two edges are not adjacent.

Input

Intput contains multiple test cases.

The first line is an integer T,1≤T≤20, the number of test cases.

Each case begins with an integer n(n≤200), indicating the number of the points.

The next n lines contains three integers xi,yi,zi, (−2000≤xi,yi,zi≤2000), representing the coordinates of the ith point.

Output

For each test case,output a line which contains"Case #x: y",x represents the xth test(starting from one),y is the number of Special Tetrahedron.

Sample Input

2
4
0 0 0
0 1 1
1 0 1
1 1 0
9
0 0 0
0 0 2
1 1 1
-1 -1 1
1 -1 1
-1 1 1
1 1 0
1 0 1
0 1 1

Sample Output

Case #1: 1
Case #2: 6

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

题意

在三维空间中,给出N个点(N<=200),定义特殊四面体为四个边等长且不等长的两边不相邻的四面体,或者六条边都相等的四面体。求特殊四面体的个数。

思路

枚举每一条线段,作为空间四边形的一条对角线,再枚举每一个点,如果这个点到上述的对角线的两个端点距离相等,将其加入这个对角线下属的集合。对于每条对角线下属的集合,枚举集合中的任意两个点C,D,现假设对角线的端点A,B,在C、D加入集合的时候,就保证了AC=AD,BC=BD 了,现在判断,如果ABCD四个点不共面并且AC=AD,这就是一个特殊四面体了。

考虑到这样枚举会让六条边都相同的四面体计数6次,其他的合法四面体会计数2次,所以我们将上述两种情况分别计数,最后算答案的时候,前者的数目除以6+后者的数目/2就是特殊四面体的个数。

 

 

HDU5733 tetrahedron 几何公式题

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

tetrahedron

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 631    Accepted Submission(s): 249
Problem Description

Given four points ABCD, if ABCD is a tetrahedron, calculate the inscribed sphere of ABCD.
 Input
Multiple test cases (test cases 100).
Each test cases contains a line of 12 integers [1e6,1e6] indicate the coordinates of four vertices of ABCD.
Input ends by EOF.
 Output
Print the coordinate of the center of the sphere and the radius, rounded to 4 decimal places.
If there is no such sphere, output "O O O O".
 Sample Input
0 0 0 2 0 0 0 0 2 0 2 0
0 0 0 2 0 0 3 0 0 4 0 0
 Sample Output
0.4226 0.4226 0.4226 0.4226
O O O O
 Author
HIT
 Source
题意:给定三维空间中四个点,如果能构成一个四面体,则输出这个四面体的内切圆的球心和半径,否则输出四个“O”。
公式:设这四个点分别为ABCD,这四个点对面的面积为SA,SB,SC,SD。其球心为
X=(Xa*SA+Xb*SB+Xc*SC+Xd*SD)/(SA+SB+SC+SD)。
Y=(Ya*SA+Yb*SB+Yc*SC+Yd*SD)/(SA+SB+SC+SD)。
Z=(Za*SA+Zb*SB+Zc*SC+Zd*SD)/(SA+SB+SC+SD)。
半径为
R=3V/(SA+SB+SC+SD)
V是这个四面体,可以用任意一个点引出的三个向量求混合积/6求得。