1216-Lost in Space

問題概要

ある三角形の3辺の長さとN個の3次元空間上の点が与えられる．
3次元上の点を3つ選んで出来る三角形と与えられた三角形と相似になるような3点を探せ．
誤差は1未満である．
(誤差については自信無いです…)

解法

点が30個以内なので全探索．
O(N^3)

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
#include <boost/format.hpp>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
struct Point{
	double x,y,z;
};
Point pts[30];
double dist(Point a,Point b){return hypot(hypot(a.x-b.x,a.y-b.y),a.z-b.z);}


int main(){
	int T;
	cin>>T;
	while(T--){
		double a,b,c;
		cin>>a>>b>>c;
		int n;
		cin>>n;
		REP(i,n){
			cin>>pts[i].x>>pts[i].y>>pts[i].z;
		}
		REP(i,n)REP(j,n){
			double q=dist(pts[i],pts[j]);
			REP(k,n){
				if(i==j||j==k||k==i)continue;
				if(abs(dist(pts[i],pts[k])/q-b/a)<1e-3){
					if(abs(dist(pts[j],pts[k])/q-c/a)<1e-3){
						cout<<boost::format("%d %d %d")%(k+1)%(j+1)%(i+1)<<endl;
						i=j=k=n;
						break;
					}
				}
			}
		}
	}
	return 0;
}