codeforces Restore Cube（暴力枚举）

1 /* 2 题意：给出立方体的每个顶点的坐标（是由源坐标三个数某几个数被交换之后得到的！）， 3 问是否可以还原出一个立方体的坐标，注意这一句话： 4 The numbers in the i-th output line must be a permutation of the numbers in i-th input line! 5 6 思路： 7 我们只要对输入的每一行数据进行枚举每一个排列， 然后检查时候能构成立方体就好了！ 8 检查立方体：找到最小的边长的长度 l， 统计边长为l， sqrt(2)*l， sqrt(3)*l的边长 9 条数，如果恰好分别为12， 12， 4那么就是立方体了... 10 */ 11 #include<iostream> 12 #include<cstdio> 13 #include<cstring> 14 #include<algorithm> 15 16 using namespace std; 17 18 typedef long long LL; 19 20 LL num[8][3], d[70]; 21 22 LL dis(int i, int j){ 23 return (num[i][0]-num[j][0])*(num[i][0]-num[j][0]) + 24 (num[i][1]-num[j][1])*(num[i][1]-num[j][1]) + 25 (num[i][2]-num[j][2])*(num[i][2]-num[j][2]); 26 } 27 28 29 void out(){ 30 for(int i=0; i<8; ++i){ 31 printf("%lld", num[i][0]); 32 for(int j=1; j<3; ++j) 33 printf(" %lld", num[i][j]); 34 printf("\n"); 35 } 36 } 37 38 int vis[8][8]; 39 40 bool check(){ 41 int cnt=0; 42 int cnt1=0, cnt2=0, cnt3=0; 43 LL L=(1LL)<<60; 44 memset(vis, 0, sizeof(vis)); 45 for(int i=0; i<8; ++i) 46 for(int j=0; j<8; ++j) 47 if(i!=j && !vis[i][j] && !vis[j][i]){ 48 d[cnt++]=dis(i, j); 49 vis[i][j]=vis[j][i]=1; 50 if(L>d[cnt-1]) 51 L=d[cnt-1]; 52 } 53 if(L==0) return false; 54 for(int i=0; i<cnt; ++i) 55 if(d[i] == L) cnt1++; 56 else if(d[i] == 2*L) cnt2++; 57 else if(d[i] == 3*L) cnt3++; 58 if(cnt1==12 && cnt2==12 && cnt3==4) return true; 59 return false; 60 } 61 62 bool dfs(int cur){ 63 if(cur>=8) return false; 64 sort(num[cur], num[cur]+3);//排序 65 do{ 66 if(check()){ 67 printf("YES\n"); 68 out(); 69 return true; 70 } 71 if(dfs(cur+1)) return true;//得到当前的全排列之后，继续向下寻找 72 }while(next_permutation(num[cur], num[cur]+3));//枚举这一个行的每一个全排列 73 return false; 74 } 75 76 int main(){ 77 for(int i=0; i<8; ++i) 78 for(int j=0; j<3; ++j) 79 scanf("%lld", &num[i][j]); 80 if(!dfs(0)) 81 printf("NO\n"); 82 return 0; 83 }

 

转载于:https://www.cnblogs.com/hujunzheng/p/3966599.html

总结

以上是生活随笔为你收集整理的codeforces Restore Cube（暴力枚举）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。