Codeforces Round #265 (Div. 2) D. Restore Cube Cube judgment_html/css_WEB-ITnose

http://codeforces.com/contest/465/problem/D

Given 8 point coordinates, for each point, you can freely exchange x, y , the value of the z coordinate. Ask if 8 points can form a cube.

Violent enumeration is enough, pay attention to check if the cube pose is not correct T

If 8 points form a cube, it is like this: find all point pairs The minimum distance between them should be equal to the length L of the side. Each vertex should have exactly three points L distance from it, and the three sides should be perpendicular to each other. If these conditions are met at every point, then it must be a cube. The checking complexity is about O(8^2).

#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <string>#include <queue>#include <vector>#include<set>#include <iostream>#include <algorithm>using namespace std;#define RD(x) scanf("%d",&x)#define RD2(x,y) scanf("%d%d",&x,&y)#define clr0(x) memset(x,0,sizeof(x))typedef long long LL;typedef pair<int, int> pii;const double eps = 1e-9;const double pi = acos(-1.0);LL dianji(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){    return x1*x2+y1*y2+z1*z2;}LL dist2(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);}LL v[8][3],minl[8],l;int cntmin[8],to[8][8];int index[8];bool chuizhi(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){    return dianji(x1,y1,z1,x2,y2,z2) == 0;}bool chuizhi(int i,int a,int b){    return chuizhi(v[a][0] - v[i][0],v[a][1] - v[i][1],v[a][2] - v[i][2],v[b][0] - v[i][0],v[b][1] - v[i][1],v[b][2] - v[i][2]);}bool chuizhi(int i,int a,int b,int c){    return chuizhi(i,a,b)&&chuizhi(i,b,c)&&chuizhi(i,a,c);}bool check(){    clr0(index),clr0(minl),clr0(cntmin);    for(int i = 0;i < 8;++i){        for(int j = i + 1;j < 8;++j){            l = dist2(v[i][0],v[i][1],v[i][2],v[j][0],v[j][1],v[j][2]);            if(!minl[i] || minl[i] > l)                minl[i] = l,to[i][cntmin[i] = 0] = j;            else if(minl[i] == l)                to[i][++cntmin[i]] = j;            if(!minl[j] || minl[j] > l)                minl[j] = l,to[j][cntmin[j] = 0] = j;            else if(minl[j] == l)                to[j][++cntmin[j]] = i;        }        if(cntmin[i]!=2 || !minl)            return false;        if(!chuizhi(i,to[i][0],to[i][1],to[i][2]))            return false;    }    return true;}bool find(int x){    if(x == 8){        return check();    }    do{        if(find(x+1))            return true;    }while(next_permutation(v[x],v[x]+3));    return false;}int main() {    for(int i = 0;i < 8;++i){        scanf("%I64d%I64d%I64d",&v[i][0],&v[i][1],&v[i][2]);        sort(v[i],v[i]+3);    }    if(!find(0))        puts("NO");    else{        puts("YES");        for(int i = 0;i < 8;++i){            printf("%I64d %I64d %I64d\n",v[i][0],v[i][1],v[i][2]);        }    }    return 0;}