计算几何水题。暴力搞
注意力全部都在02那里,完全没想这道题!
/*--------------------------------------------------------------------------------------*/ #include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map> //debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const int prime = ;
const int MOD = 1e9+; /*--------------------------------------------------------------------------------------*/
using namespace std; const int maxn = ;
int N,M,T; struct point{
int x,y,z;
point(int _x=,int _y=,int _z=):x(_x),y(_y),z(_z){} bool operator < (const point &rhs) const
{
if(y == rhs.y && x == rhs.x) return z < rhs.z;
else if(x == rhs.x) return y < rhs.y;
else return x < rhs.x;
}
point operator + (const point B) const
{
return point(x+B.x,y+B.y,z+B.z);
}
point operator - (const point B) const
{
return point(x-B.x,y-B.y,z-B.z);
}
int operator * (const point B) const
{
return x*B.x + y*B.y + z*B.z;
}
point operator ^ (const point B) const
{
return point(y*B.z - z*B.y,
z*B.x - x*B.z,
x*B.y - y*B.x);
}
}pt[maxn];
typedef point vec; struct node{
int id;
int dis;
bool operator < (const node &rhs) const
{
return dis < rhs.dis;
}
}; int dis(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);
}
bool onPlane(point a,point b,point c,point d)
{
return ( ((a-c) ^ (a-d)) * (a-b) ) == ;
}
int _onPlane(point a,point b,point c,point d)
{
return ( ((a-c) ^ (a-d)) * (a-b) ) ;
} vector <node> ppt[maxn];
unordered_set <int > st; int myHash(LL a,LL b,LL c,LL d)
{
return ((((a*prime%MOD + b)*prime%MOD +c)*prime%MOD +d) + MOD )%MOD;
} int cas;
int main()
{
//freopen("input","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=,x,y,z;i<N;i++)
{
scanf("%d%d%d",&x,&y,&z);
pt[i].x = x;
pt[i].y = y;
pt[i].z = z;
} st.clear();
for(int i=;i<N;i++)
{
node tmp;
ppt[i].clear();
for(int j=;j < N;j++) if(i != j)
{
tmp.dis = dis(pt[i],pt[j]);
tmp.id = j;
ppt[i].push_back(tmp);
}
sort(ppt[i].begin(),ppt[i].end());
} int ans = ;
int save[];
for(int i=;i<N;i++)
{
for(int j=i+;j<N;j++)
{
//printf("now use:%d %d\n",i,j);
for(int k=;k<ppt[i].size();k++) if(ppt[i][k].id != j)
{
for(int h=k+;h<ppt[i].size() && ppt[i][k].dis == ppt[i][h].dis;h++) if(ppt[i][h].id != j)
{
if(dis(pt[j],pt[ppt[i][h].id]) == dis(pt[j],pt[ppt[i][k].id]) && dis(pt[j],pt[ppt[i][h].id]) == ppt[i][k].dis)
{
if(onPlane(pt[i],pt[j],pt[ppt[i][k].id],pt[ppt[i][h].id]) ) continue;
//int s = myhash(i,j,ppt[i][k].id,ppt[i][h].id);
//printf("%d %d %d %d\n",i,j,ppt[i][k].id,ppt[i][h].id);
vector <int> ve;
ve.push_back(i);
ve.push_back(j);
ve.push_back(ppt[i][k].id);
ve.push_back(ppt[i][h].id);
sort(ve.begin(),ve.end());
int s = myHash(ve[],ve[],ve[],ve[]);
if(st.find(s) == st.end())
{
st.insert(s);
//printf("%d %d %d %d\n",i,j,ppt[i][k].id,ppt[i][h].id);
//printf("%d\n",_onPlane(pt[i],pt[j],pt[ppt[i][k].id],pt[ppt[i][h].id]));
ans++;
} }
}
}
}
} printf("Case #%d: %d\n",++cas,ans);
}
}