AOJ 1216 Lost in Space

Lost in Space
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1216

問題概要

三角形の３辺の長さが与えられる。
次に、三次元座標でいくつか点が与えられる。
それらの点で最初の三角形と相似になるような三角形を構成する３点を求めよ。

解法

全探索。

ソース

#include <cmath>
#include <iostream>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)


using namespace std;

class Point{
public:
  double x, y, z;
};

double getDistance(Point a, Point b){
  double tmp = abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y);
  return sqrt(tmp   + abs(a.z - b.z) * abs(a.z - b.z));
}

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    vector<double> original(3);
    rep(i, 3)cin >> original[i];
    int n;
    cin >> n;
    vector<Point> V(n);
    rep(i, n){
      double x, y, z;
      cin >> x >> y >> z;
      V[i] = (Point){x, y, z};
    }
    
    rep(p, n){
      rep(q, n){
        if(p == q)continue;
        rep(r, n){
          if(r == p || q == r)continue;
          vector<double> now;
          now.push_back(getDistance(V[q], V[r]));
          now.push_back(getDistance(V[r], V[p]));
          now.push_back(getDistance(V[p], V[q]));
          bool ok = true;
          rep(i, 3){
            rep(j, 3){
              if(abs(now[i] / now[j] - original[i] / original[j]) > 0.0002){
                ok = false;
              }
            }
          }
          if(ok){
            cout << p + 1 << ' ' << q +1 << ' ' << r+1 << endl;
          }
        }
      }
    }
  }
  return 0;
}