题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5839
题意: 就是给你n个必定不同的点,求唯一四面体, 条件: 1,至少4条边相等. 2,如果刚好有4条边相等,那么就判断另外两条边必须不相邻的.
个人感想: 数据很弱…O（n4）都可以过,马丹,这种数学我n早就忘记了7788,实在无力,我也就想到了n4的算法了.我的想法很简单.
1.随机拿3个点,判断是否共线,（马丹我叉积怎么判共线我都不知道了…我尼玛我都不知道这样写是不是对的.）
2.然后这3个点组成的边是不是等腰或者等边三角形,而且必然需要.画图。(这是用来剪枝的) 如何的图最差的情况必须是这样
3.判断4点是否共面.
4.如果>5 ans++;
5.如果=4，判断两条不相同的边是否在对位.（0，4） （1，5） （2，3）.
比赛的时候并不敢写啊…我总觉得必然超时…然后挂机3小时,早知道拼一拼还有可能… 随意啦…
分析:计算几何
代码:
/* Author:GavinjouElephant * Title: * Number: * main meanning： * * * */ #include <iostream> using namespace std; #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <sstream> #include <cctype> #include <vector> #include <set> #include <cstdlib> #include <map> #include <queue> //#include<initializer_list> //#include <windows.h> //#include <fstream> //#include <conio.h> #define MaxN 0x7fffffff #define MinN -0x7fffffff #define lson 2*k #define rson 2*k+1 typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=205; int Scan()//读入整数外挂. { int res = 0, ch, flag = 0; if((ch = getchar()) == '-') //判断正负 flag = 1; else if(ch >= '0' && ch <= '9') //得到完整的数 res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9' ) res = res * 10 + ch - '0'; return flag ? -res : res; } void Out(int a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } class point { public: int x; int y; int z; }; int T; int N; point p[maxn]; bool isonLine(int i,int j,int k) { int ax=p[j].x-p[i].x; int ay=p[j].y-p[i].y; int az=p[j].z-p[i].z; int bx=p[k].x-p[i].x; int by=p[k].y-p[i].y; int bz=p[k].z-p[i].z; int tx=(ay*bz-az*by); int ty=(az*bx-ax*bz); int tz=(ax*by-ay*bx); int ans=tx*tx+ty*ty+tz*tz; if(ans==0)return true; return false; } int dis(int i,int j) { int x=p[j].x-p[i].x; int y=p[j].y-p[i].y; int z=p[j].z-p[i].z; return x*x+y*y+z*z; } bool isonFace(int i,int j,int k,int l) { point s1,s2,s3; s1.x=p[j].x-p[i].x;s1.y=p[j].y-p[i].y;s1.z=p[j].z-p[i].z; s2.x=p[k].x-p[i].x;s2.y=p[k].y-p[i].y;s2.z=p[k].z-p[i].z; s3.x=p[l].x-p[i].x;s3.y=p[l].y-p[i].y;s3.z=p[l].z-p[i].z; int ans=s1.x*s2.y*s3.z+s1.y*s2.z*s3.x+s1.z*s2.x*s3.y-s1.z*s2.y*s3.x-s1.x*s2.z*s3.y-s1.y*s2.x*s3.z; if(ans == 0) return true; return false; } int a[6]; int a2[6]; int main() { #ifndef ONLINE_JUDGE freopen("coco.txt","r",stdin); freopen("lala.txt","w",stdout); #endif scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d",&N); int ans=0; int num; int len; 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++) { for(int k=j+1;k<=N;k++) { if(isonLine(i,j,k))continue; a[0]=dis(i,j); a[1]=dis(i,k); a[3]=dis(j,k); if(a[0]==a[1]&&a[1]==a[3]){len=a[0];} else if(a[0]==a[1]){len=a[0];} else if(a[0]==a[3]){len=a[0];} else if(a[1]==a[3]){len=a[1];} else continue; for(int l=k+1;l<=N;l++) { if(isonFace(i,j,k,l))continue; a[2]=dis(i,l); a[4]=dis(k,l); a[5]=dis(j,l); num=0; for(int i=0;i<6;i++) { if(a[i]==len){num++;} } if(num>4){ans++;} else if(num==4) { int p,ll,rr; bool flag=true; for(p=0;p<6;p++) { if(a[p]!=len) { if(flag){ll=p;flag=false;} else rr=p; } } if(ll==0&&rr==4||ll==1&&rr==5||ll==2&&rr==3)ans++; } } } } } printf("Case #%d: %d\n",cas,ans); } return 0; }