5839Special Tetrahedron---hdu5839（计算几何，求特殊四面体个数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5839

给你n个三维的点，然后求这n各点可以构成多少个特殊四面体，特殊四面体满足一下两点；

1.至少有四条面相等；

2.如果只有四条边相等，那么剩下的两条边不相邻；

n的范围是300；

暴力枚举四面体的其中一条边的两点，然后让另外两点到这两点的距离相等，判断一下这四个点是否共面；

还有如果能构成四面体看一下是否是正四面体，如果是正四面体，则六条边都会能枚举一边，结果的一部分是正六面体的个数/6；否则则是不相等的那对对棱枚举两次所以要/2；

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
#define N 500
#define met(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef long long LL;

struct Point
{
    int x, y, z;
};

double Dist(Point a, Point b)///求两点间的距离；
{
    double ans = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
    return ans;
}

bool Judge(Point a, Point b, Point c, Point d)///判断四点是否共面；共面返回真；
{
    Point s1, s2, s3;

    s1.x = b.x - a.x; s1.y = b.y - a.y; s1.z = b.z - a.z;
    s2.x = c.x - a.x; s2.y = c.y - a.y; s2.z = c.z - a.z;
    s3.x = d.x - a.x; s3.y = d.y - a.y; s3.z = d.z - a.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;

    return ans == 0;
}
/*
ans = 下面行列式的值;
s1.x s2.x s3.x
s1.y s2.y s3.y
s1.z s2.z s3.z
*/

int main()
{
    int T, t = 1, n;
    scanf("%d", &T);
    while(T--)
    {
        Point a[N];

        scanf("%d", &n);

        for(int i=1; i<=n; i++)
            scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);

        int ans1 = 0, ans2 = 0;

        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                Point t[N];
                int cnt = 0;
                for(int k=1; k<=n; k++)
                {
                    if(k==i || k==j)continue;
                    if(Dist(a[k], a[i]) != Dist(a[k], a[j]))continue;
                    t[cnt++] = a[k];
                }
                if(cnt < 2)continue;
                for(int p=0; p<cnt; p++)
                {
                    for(int q=p+1; q<cnt; q++)
                    {
                        if(Judge(a[i], a[j], t[p], t[q]))continue;
                        if(Dist(a[i], t[p]) != Dist(t[q], a[i]))continue;
                        if(Dist(a[i], a[j]) == Dist(t[p], t[q]) && Dist(a[i], a[j]) == Dist(t[p], a[i]))
                            ans1++;///正四面体个数；
                        else
                            ans2++;///有四条边相等的四面体个数；
                    }
                }
            }
        }
        printf("Case #%d: %d
", t++, ans1/6 + ans2/2);
    }
    return 0;
}