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 }