Codeforces #265 Div1 B. Restore Cube

問題

8点の座標が与えられるので(x,y,z)を自由に並びかえたとき立方体の頂点できるか判定せよ。

問題リンク：http://codeforces.com/problemset/problem/465/D

解法

各点の座標の並べ方は $3! = 6$ 通り。1点固定して他を全探索しても高々 $6^{7}$ 通りなので全探索できる。

あとは8点の座標が与えられたときにそれらが立方体の頂点になっているかを判定すればよい。

自分は、

8点の座標の平均となる点をOとして、Oから各点までの距離がすべて等しい
各点から異なる点への距離を求め、そのうち小さい3つの距離がすべて等しい

を満たすとき立方体としたらACできた。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr double EPS = 1e-9;

int n = 8;
vector<vector<int> > pos(n, vector<int>(3)), tmp(n, vector<int>(3));

double dist(vector<int> &p){
    return sqrt(pow(p[0],2)+pow(p[1],2)+pow(p[2],2));
}

double dist(vector<int> &p, vector<int> &q){
    return sqrt(pow(p[0]-q[0],2)+pow(p[1]-q[1],2)+pow(p[2]-q[2],2));
}

bool isCube(){
    int OX = 0, OY = 0, OZ = 0;
    for(int i=0;i<n;i++){
        OX += pos[i][0];
        OY += pos[i][1];
        OZ += pos[i][2];
    }
    OX /= 8;
    OY /= 8;
    OZ /= 8;
    for(int i=0;i<n;i++){
        tmp[i][0] = pos[i][0]-OX;
        tmp[i][1] = pos[i][1]-OY;
        tmp[i][2] = pos[i][2]-OZ;
    }
    vector<double> d(n);
    for(int i=0;i<n;i++){
        d[i] = dist(tmp[i]);
    }
    sort(d.begin(), d.end());
    if(abs(d.back() - d.front()) > EPS) return false;
    for(int i=0;i<n;i++){
        d.clear();
        for(int j=0;j<n;j++){
            if(i==j) continue;
            d.emplace_back(dist(tmp[i], tmp[j]));
        }
        sort(d.begin(),d.end());
        if(abs(d[2]-d[0])>EPS) return false;
    }
    return true;
}

bool rec(int i){
    if(i == n){
        if(isCube()){
            cout << "YES\n";
            for(int j=0;j<n;j++){
                for(int k=0;k<3;k++){
                    cout << pos[j][k]/8 << " \n"[k==2];
                }
            }
            return true;
        }else{
            return false;
        }
    }
    sort(pos[i].begin(),pos[i].end());
    while(1){
        bool ok = true;
        for(int j=0;j<i;j++){
            if(pos[j]==pos[i]) ok = false;
        }
        if(ok && rec(i+1)) return true;
        if(!next_permutation(pos[i].begin(),pos[i].end())){
            break;
        }
    }
    return false;
}

int solve(){
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin >> pos[i][j];
            pos[i][j] *= 8;
        }
    }
    if(!rec(1)){
        cout << "NO\n";
    }
    return 0;
}

int main(){
    solve();
    return 0;
}