浙江财经大学
信息管理与工程学院

HDU 5839 Special Tetrahedron

本文由 Ocrosoft 于 2016-08-15 22:36:21 发表

Special Tetrahedron

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 523    Accepted Submission(s): 222

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
n^4都能1200MS过(时限2000MS),数据也真是水…

题意:给出n个空间中的点,保证不重合,求能够组成的四面体的个数。四面体要求满足:
1.至少4条边相等。
2.如果是4条边相等,不相等的两条边需要不相邻。

思路:n^4暴力枚举…好像有n^3的,有空再补上吧。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 200 + 10;
using namespace std;
struct P
{
	int x, y, z;
}p[MAXN];
bool isonline(int i, int j, int k)//共线判断
{
	int ax = p[j].x - p[i].x;
	int ay = p[j].y - p[i].y;
	int az = p[j].z - p[i].z;

	int bx = p[k].x - p[i].x;
	int by = p[k].y - p[i].y;
	int bz = p[k].z - p[i].z;

	int tx = (ay*bz - az*by);
	int ty = (az*bx - ax*bz);
	int tz = (ax*by - ay*bx);

	int ans = tx*tx + ty*ty + tz*tz;

	if (ans == 0)return true;
	return false;
}
int dis(int i, int j)//两点距离计算
{
	int x = p[j].x - p[i].x;
	int y = p[j].y - p[i].y;
	int z = p[j].z - p[i].z;
	return x*x + y*y + z*z;
}
bool isonface(int i, int j, int k, int l)//三点共面判断
{
	P s1, s2, s3;
	s1.x = p[j].x - p[i].x; s1.y = p[j].y - p[i].y; s1.z = p[j].z - p[i].z;
	s2.x = p[k].x - p[i].x; s2.y = p[k].y - p[i].y; s2.z = p[k].z - p[i].z;
	s3.x = p[l].x - p[i].x; s3.y = p[l].y - p[i].y; s3.z = p[l].z - p[i].z;
	int ans = s1.x*s2.y*s3.z + s1.y*s2.z*s3.x + s1.z*s2.x*s3.y - s1.z*s2.y*s3.x - s1.x*s2.z*s3.y - s1.y*s2.x*s3.z;
	if (ans == 0) return true;
	return false;
}

int main()
{
	int T, cas = 1;
	cin >> T;
	while (T--)
	{
		int n, a[6], ans = 0;
		cin >> n;
		for (int i = 1; i <= n; i++)
			scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
		for (int i = 1; i <= n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				for (int k = j + 1; k <= n; k++)
				{
					if (isonline(i, j, k))continue;//三点共线
					a[0] = dis(i, j);//计算三条边,前两条边作为底边
					a[1] = dis(i, k);//第三条边如果也作为底边,如果三边相等的时候,
					a[3] = dis(j, k);//剩下三条边任意两条都是相邻的,会不满足条件
					int len;
					if (a[0] == a[1] && a[1] == a[3])len = a[0];//三边相等
					else if (a[0] == a[1])len = a[0];//其中两条边相等
					else if (a[0] == a[3])len = a[0];
					else if (a[1] == a[3])len = a[1];
					else continue;
					for (int l = k + 1; l <= n; l++)
					{
						if (isonface(i, j, k, l))continue;//四点共面
						a[2] = dis(i, l);
						a[4] = dis(k, l);
						a[5] = dis(j, l);
						int cnt = 0;
						for (int r = 0; r < 6; r++)
							if (a[r] == len)cnt++;//计算相等的边
						if (cnt > 4)ans++;//大于4条边相等肯定满足
						else if (cnt == 4)//如果刚好是4条边,要满足不等的两条边不相邻,画幅图会比较直观
						{
							int ii, ll, rr;
							bool f = 1;
							for (ii = 0; ii < 6; ii++)
							{
								if (a[ii] != len)
								{
									if (f) { ll = ii; f = 0; }
									else rr = ii;
								}
							}
							if (ll == 0 && rr == 4 || ll == 1 && rr == 5 || ll == 2 && rr == 3)ans++;
						}
					}
				}
			}
		}
		printf("Case #%d: %d\n", cas++, ans);
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 5839 Special Tetrahedron

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址