HDU 5839 Special Tetrahedron（计算几何）

【题意】<big>在三维空间中给出N个点，找有多少个满足条件的四面体.</big>

四面体至少有四条边相等
<big>若恰好四条边相等，那么剩下的两边不相邻.</big>

【解题方法】

<big>四面体中每条边仅有一条边与它不相邻, 可以转化一下题目的条件：
寻找四边相等的空间四边形(不能四点共面).
首先枚举该空间四边形中的一条对角线，再计算剩余的点跟这条对角线两端点的距离.
若某点与这对角线两端点的距离相等, 则添加到一个集合中.
枚举集合中的任意两点，与对角线两端点组成一个四边形. 判断该四边形是否符合条件：
首先集合中两点到对角线端点的距离要相等. 其次，这四点要不共面.

在上述判断过程中会出现重复计数：
由于每个四边形有两条对角线，所以在枚举对角形计数时，每个四边形都被计数了两次.
特殊的：如果一个四面体是正四面体，那么这四个点被计数了6次. (每条边都计数一次)
所以在处理过程中要记录出现了几次正四面体.
每当枚举到一个合法的空间四面体时，求一下剩下两条边是否跟其它边相等. 如果相等则计数.
令rep为上述计数次数， rep/6 为正四面体的个数(每个正四面体会计数6次).
根据上述分析， ans/2 - 2*rep/6 即为最后结果.

关于时间复杂度：
上述过程看起来是 O(N^4).
而实际上，每次枚举对角线时，符合条件的点一定在这条对角线的中垂面上.
所以不可能每次枚举对角线时，都有很多点在中垂面上. 所以均摊复杂度并不高.</big>

【AC 代码】

//
//Created BY Just_sort 2016/8/15
//All Rights Reserved
//

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
struct point{
    LL x,y,z;
}p[205];
int n;
LL getdis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
point cross(point a,point b)
{
    point ret;
    ret.x=a.y*b.z-b.y*a.z;
    ret.y=a.z*b.x-a.x*b.z;
    ret.z=a.x*b.y-a.y*b.x;
    return ret;
}
point subt(point a,point b)
{
    point ret;
    ret.x=a.x-b.x;
    ret.y=a.y-b.y;
    ret.z=a.z-b.z;
    return ret;
}
LL multi(point a,point b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
point fa(point s1,point s2,point s3)
{
    return cross(subt(s1,s2),subt(s2,s3));
}
bool isok(point a,point b,point c,point d)
{
    return multi(fa(a,b,c),subt(d,a))==0;
}
struct node{
    int id;
    LL dis;
};
vector<node>v;
int main()
{
    int T,n,cas=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1; i<=n; i++){
            scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
        }
        int ans=0,cnt=0;
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                v.clear();
                for(int k=1; k<=n; k++){
                    if(getdis(p[k],p[i])==getdis(p[k],p[j])) v.push_back(node{k,getdis(p[k],p[j])});
                }
                int sz=v.size();
                for(int ii=0; ii<sz; ii++){
                    for(int jj=ii+1; jj<sz; jj++){
                        if(v[ii].dis!=v[jj].dis) continue;
                        if(isok(p[i],p[j],p[v[ii].id],p[v[jj].id])) continue;
                        ans++;
                        if(getdis(p[i],p[j])==v[ii].dis&&v[ii].dis==getdis(p[v[ii].id],p[v[jj].id])) cnt++;
                    }
                }
            }
        }
        ans/=2;
        ans-=2*cnt/6;
        printf("Case #%d: %d\n",cas++,ans);
    }
    return 0;
}