AOJ1216 Lost in Space

AOJ Volume12

問題リンク Lost in Space

  • 概要

三角形の辺の長さQR, RP, PQ(cm)と、N個の3次元座標が与えられる。
N個の中の3点を使い、与えられた三角形と相似になる三角形を作る点の番号を答えよ。
相似とは、三角形の中の全ての2辺の比が、与えられた三角形のそれと誤差が0.01%に収まるものをいう。
3 <= N <= 30

  • 解法

1光年は9.461*10^12(km)だなんて書いてありますが、どうせ比を取るので光年をkmに直す必要はないです。
r1 = QR/RP
r2 = RP/PQ
r3 = PQ/QR
とします。
Nの大きさが30しかないので三角形の3頂点を全て試します。そのときの比をr1, r2, r3と同様にR1, R2, R3とします。
これらの差の絶対値が0.0001に収まればそれらが求めたい三角形になっています。

  • ソース
import java.util.Scanner;

//Lost in Space
public class AOJ1216 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		double RATIO = 1e-4;
		while(t--!=0){
			double qr = sc.nextDouble(), rp = sc.nextDouble(), pq = sc.nextDouble();
			double r1 = qr/rp, r2 = rp/pq, r3 = pq/qr;
			int n = sc.nextInt();
			double[] x = new double[n+1], y = new double[n+1], z = new double[n+1];
			for(int i=1;i<=n;i++){
				x[i] = sc.nextDouble(); y[i] = sc.nextDouble(); z[i] = sc.nextDouble();
			}
			for(int p=1;p<=n;p++)for(int q=1;q<=n;q++)for(int r=1;r<=n;r++){
				if(p==q||q==r||r==p)continue;
				double QR = Math.sqrt(Math.pow(x[q]-x[r], 2)+Math.pow(y[q]-y[r], 2)+Math.pow(z[q]-z[r], 2));
				double RP = Math.sqrt(Math.pow(x[p]-x[r], 2)+Math.pow(y[p]-y[r], 2)+Math.pow(z[p]-z[r], 2));
				double PQ = Math.sqrt(Math.pow(x[q]-x[p], 2)+Math.pow(y[q]-y[p], 2)+Math.pow(z[q]-z[p], 2));
				double R1 = QR/RP, R2 = RP/PQ, R3 = PQ/QR;
				double d1 = Math.abs(r1-R1), d2 = Math.abs(r2-R2), d3 = Math.abs(r3-R3);
				if(d1<RATIO && d2<RATIO && d3<RATIO){
					System.out.println(p+" "+q+" "+r);break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1216().run();
	}
}