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 == ;

}

/*

ans = 下面行列式的值;

s1.x s2.x s3.x

s1.y s2.y s3.y

s1.z s2.z s3.z

*/

int main()

{

    int T, t = , n;

    scanf("%d", &T);

    while(T--)

    {

        Point a[N];

        scanf("%d", &n);

        for(int i=; i<=n; i++)

            scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);

        int ans1 = , ans2 = ;

        for(int i=; i<=n; i++)

        {

            for(int j=i+; j<=n; j++)

            {

                Point t[N];

                int cnt = ;

                for(int k=; 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 < )continue;

                for(int p=; p<cnt; p++)

                {

                    for(int q=p+; 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\n", t++, ans1/ + ans2/);

    }

    return ;

}