【2016-CCPC-H】计算几何（Special Tetrahedron，hdu 5839）

http://www.cnblogs.com/Sunshine-tcf/p/5770545.html

本来暴力枚举O（n^4）铁定超时的。

但是这种方法枚举得很有技巧。

前两层是暴力枚举，

第三层筛选，第四层在筛选的结果中枚举。

前三层是O（n^3），

第四层在筛选出来的点中枚举，枚举量十分小，可以理解为常数极小的O（n^4）。

还要考虑清楚各种情况下重复或错误的枚举。

四点共面的判断等。

此题非常值得学习。

要学会抓住题目的特殊信息。

比如：这个四边形的要求为何是这样的，而不是随便的？是不是因为这样就可以用特殊的方法枚举?

#include<bits/stdc++.h>
#define maxn 220
using namespace std;

int n;

struct pt
{
    int x,y,z;
};
pt p[maxn];

int dist(int a1,int a2)
{
    pt a=p[a1];
    pt b=p[a2];
    int x=a.x-b.x;
    int y=a.y-b.y;
    int z=a.z-b.z;
    return x*x+y*y+z*z;
}

pt xl(pt a,pt b)
{
    pt c;
    c.x=b.x-a.x;
    c.y=b.y-a.y;
    c.z=b.z-a.z;
    return c;
}

pt cx(pt a,pt b)
{
    pt c;
    c.x=a.y*b.z-a.z*b.y;
    c.y=a.z*b.x-a.x*b.z;
    c.z=a.x*b.y-a.y*b.x;
    return c;
}

bool gm(int a1,int a2,int a3,int a4)
{
    pt a,b,c,d;
    a=p[a1];
    b=p[a2];
    c=p[a3];
    d=p[a4];
    pt ac,ad,bc,bd;
    ac=xl(a,c);
    ad=xl(a,d);
    bc=xl(b,c);
    bd=xl(b,d);
    pt xl1=cx(ac,ad);
    pt xl2=cx(bc,bd);
    pt ans=cx(xl1,xl2);
    if(ans.x==0&&ans.y==0&&ans.z==0) return true;
    else return false;
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        int cnt=0;
        int zheng=0;
        scanf("%d",&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++)
            {
                vector<int>vec;
                for(int k=1;k<=n;k++)
                {
                    if(k==i||k==j) continue;
                    if(dist(i,k)==dist(j,k)) vec.push_back(k);
                }
                for(unsigned int u=0;u<vec.size();u++)
                    for(unsigned int v=u+1;v<vec.size();v++)
                        if(dist(i,vec[u])==dist(i,vec[v]))
                        {
                            if(gm(i,j,vec[u],vec[v])) continue;
                            cnt++;
                            if(dist(i,j)==dist(vec[u],vec[v])&&dist(i,j)==dist(i,vec[u]))
                                zheng++;
                        }
            }
        printf("Case #%d: %d\n",t,cnt/2-zheng/3);
    }
    return 0;
}