2016CCPC网预08

HDU 5839 Special Tetrahedron

三维计算几何，暴枚

传送门：HDU

---

题意

给空间直角坐标系的一些点，问有多少四面体满足：至少有4条边相等，若恰有4条边相等，则不相等的两条边不相邻。

---

思路

虽然2000个点，但是暴力就能过，O( n4 )，大概是三维计算几何本身就麻烦吧。先二重循环枚举两个点i，j，获得一条棱，然后在一个循环，枚举所有点，若这点k到i和j距离相等，那么记录点k编号和距离到数组P。处理完所有点后再二重循环，枚举数组P里面的点，如果两个点x，y到i，j的距离都相等，且四点不共面，那么可以构成四面体。特判一下是不是正四面体。最后，一个4边或5边相等的四面体会被枚举两次（不等的那条边和它的对边作为ij各被枚举一次），正四面体被枚举6次，去重即可。

---

代码

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAXN=2007; const double eps=1e-8; typedef long long LL; int sgn(double x)//符号函数 { if(fabs(x) < eps) return 0; if(x < 0) return -1; else return 1; } //点,向量 struct Point_3 { LL x,y,z; Point_3(){} Point_3(double _x,double _y,double _z)//构造 { x=_x; y=_y;z=_z; } Point_3 operator -(const Point_3 &b)const { return Point_3(x-b.x,y-b.y,z-b.z); } Point_3 operator ^(const Point_3 &b)const//叉积 { return Point_3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x); } LL operator *(const Point_3 &b)const//点积 { return x*b.x+y*b.y+z*b.z; } friend LL operator &(const Point_3 &a,const Point_3 &b)//叉积的模 { return sqrt((a^b)*(a^b)); } }; LL lenth(Point_3 a,Point_3 b)//求两点距离 { return((a-b)*(a-b)); } bool in_a_surface(Point_3 a,Point_3 b,Point_3 c,Point_3 d)//混合积判段四面体体积，为0就是共面 { if((d-a)*((b-a)^(c-a))==0) return 1; else return 0; } Point_3 p[MAXN]; typedef pair<LL,int> P; int main() { int T; scanf("%d",&T); for(int t=1;t<=T;t++) { int n; scanf("%d",&n); memset(p,0,sizeof(p)); for(int i=0;i<n;i++) { scanf("%lld%lld%lld",&(p[i].x),&(p[i].y),&(p[i].z)); } int res=0,res6=0;//res是四面体数，res6是6边相等的四面体数 for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++)//枚举两个点构成一条边 { P cnt[MAXN];//记录到这两个点距离相等的点们 memset(cnt,0,sizeof(cnt)); int cntn=0; LL dis=lenth(p[i],p[j]); for(int k=0;k<n;k++) { LL dis1=lenth(p[i],p[k]); LL dis2=lenth(p[j],p[k]); if(dis1==dis2) { cnt[cntn].first=dis1; cnt[cntn++].second=k; } } for(int k=0;k<cntn;k++) { for(int kk=k+1;kk<cntn;kk++) { if(cnt[k].first!=cnt[kk].first) continue; if(in_a_surface(p[i],p[j],p[cnt[k].second],p[cnt[kk].second])) continue; res++; LL tmp=lenth(p[cnt[k].second],p[cnt[kk].second]); if(cnt[k].first==tmp&&tmp==dis) res6++; } } } } res/=2;//非6边相等的四面体被枚举2次 res-=res6/3;//6边相等的四面体被枚举6次 上面除过2了这里除3就行了 printf("Case #%d: %d\n",t,res); } return 0; }