【参考BLOG】点击打开链接
【题意】在三维空间中给出N个点，找有多少个满足条件的四面体.
四面体至少有四条边相等若恰好四条边相等，那么剩下的两边不相邻. 【解题方法】四面体中每条边仅有一条边与它不相邻, 可以转化一下题目的条件： 寻找四边相等的空间四边形(不能四点共面). 首先枚举该空间四边形中的一条对角线，再计算剩余的点跟这条对角线两端点的距离. 若某点与这对角线两端点的距离相等, 则添加到一个集合中. 枚举集合中的任意两点，与对角线两端点组成一个四边形. 判断该四边形是否符合条件： 首先集合中两点到对角线端点的距离要相等. 其次，这四点要不共面. 在上述判断过程中会出现重复计数： 由于每个四边形有两条对角线，所以在枚举对角形计数时，每个四边形都被计数了两次. 特殊的：如果一个四面体是正四面体，那么这四个点被计数了6次. (每条边都计数一次) 所以在处理过程中要记录出现了几次正四面体. 每当枚举到一个合法的空间四面体时，求一下剩下两条边是否跟其它边相等. 如果相等则计数. 令rep为上述计数次数， rep/6 为正四面体的个数(每个正四面体会计数6次). 根据上述分析， ans/2 - 2*rep/6 即为最后结果. 关于时间复杂度： 上述过程看起来是 O(N^4). 而实际上，每次枚举对角线时，符合条件的点一定在这条对角线的中垂面上. 所以不可能每次枚举对角线时，都有很多点在中垂面上. 所以均摊复杂度并不高.
【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; }