codeforces Restore Cube(暴力枚举)

简介:

/*
    题意:给出立方体的每个顶点的坐标(是由源坐标三个数某几个数被交换之后得到的!), 
    问是否可以还原出一个立方体的坐标,注意这一句话:
    The numbers in the i-th output line must be a permutation of the numbers in i-th input line!
    
    思路:
          我们只要对输入的每一行数据进行枚举每一个排列, 然后检查时候能构成立方体就好了! 
          检查立方体:找到最小的边长的长度 l, 统计边长为l, sqrt(2)*l, sqrt(3)*l的边长
          条数,如果恰好分别为12, 12, 4那么就是立方体了... 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

LL num[8][3], d[70];

LL dis(int i, int j){
    return  (num[i][0]-num[j][0])*(num[i][0]-num[j][0]) +
            (num[i][1]-num[j][1])*(num[i][1]-num[j][1]) + 
            (num[i][2]-num[j][2])*(num[i][2]-num[j][2]);
}


void out(){
    for(int i=0; i<8; ++i){
        printf("%lld", num[i][0]);
         for(int j=1; j<3; ++j)
             printf(" %lld", num[i][j]);
         printf("\n");
    }
}

int vis[8][8]; 

bool check(){
    int cnt=0;
    int cnt1=0, cnt2=0, cnt3=0;
    LL L=(1LL)<<60;
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<8; ++i)
        for(int j=0; j<8; ++j)
             if(i!=j && !vis[i][j] && !vis[j][i]){
                 d[cnt++]=dis(i, j);
                 vis[i][j]=vis[j][i]=1;
                 if(L>d[cnt-1])
                    L=d[cnt-1];
            }
    if(L==0) return false;
    for(int i=0; i<cnt; ++i)
        if(d[i] == L) cnt1++;
        else if(d[i] == 2*L) cnt2++;
        else if(d[i] == 3*L) cnt3++;
    if(cnt1==12 && cnt2==12 && cnt3==4) return true;
    return false; 
}

bool dfs(int cur){
    if(cur>=8) return false;
    sort(num[cur], num[cur]+3);//排序 
    do{
        if(check()){
            printf("YES\n");
            out();
            return true;
        }
        if(dfs(cur+1)) return true;//得到当前的全排列之后,继续向下寻找 
    }while(next_permutation(num[cur], num[cur]+3));//枚举这一个行的每一个全排列 
    return false;
}

int main(){
    for(int i=0; i<8; ++i)
        for(int j=0; j<3; ++j)
            scanf("%lld", &num[i][j]);
    if(!dfs(0))
       printf("NO\n");
    return 0;
}

目录
相关文章
|
机器学习/深度学习 人工智能 BI
The Great Hero(Codeforces Round #700 (Div. 2))模拟+贪心思想和排序
The Great Hero(Codeforces Round #700 (Div. 2))模拟+贪心思想和排序
60 0
|
网络架构
Codeforces Round #755 D. Guess the Permutation(交互 二分)
Codeforces Round #755 D. Guess the Permutation(交互 二分)
89 0
|
人工智能 vr&ar
SPOJ - COT Count on a tree(主席树 LCA)
SPOJ - COT Count on a tree(主席树 LCA)
93 0