Aizu Online Judge 1216 Lost in Space

■1216 Lost in Space

全探索で間に合う．
元の三角形の辺の長さをd[i]とする．
与えられた座標軍からある3点を選び，それぞれの辺の長さをe[i]とする．
この時，それぞれの辺の比r[i]は，
r[i]=e[i]/d[i]
となる．
それぞれの比の誤差が，0.1%以上になることは無い，というのだから，任意のi，jに対して，
|r[i]-r[j]|/r[i] < 0.1
となる．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  double[] d;  
17.  P[] ps;  
18.  int n;  
19.   
20.  void run(){  
21.   d=new double[3];  
22.   for(int t=sc.nextInt(); t>0; t--){  
23.    for(int i=0; i<3; i++){  
24.     d[i]=sc.nextDouble();  
25.    }  
26.    n=sc.nextInt();  
27.    ps=new P[n];  
28.    for(int i=0; i<n; i++){  
29.     double x=sc.nextDouble();  
30.     double y=sc.nextDouble();  
31.     double z=sc.nextDouble();  
32.     ps[i]=new P(x, y, z);  
33.    }  
34.    solve();  
35.   }  
36.  }  
37.   
38.  void solve(){  
39.   double[] len={0, 0, 0};  
40.   for(int c=0; c<n; c++){  
41.    for(int b=0; b<n; b++){  
42.     if(b==c){  
43.      continue;  
44.     }  
45.     for(int a=0; a<n; a++){  
46.      if(a==b||a==c){  
47.       continue;  
48.      }  
49.      len[0]=ps[b].sub(ps[c]).abs()/d[0];  
50.      len[1]=ps[c].sub(ps[a]).abs()/d[1];  
51.      len[2]=ps[a].sub(ps[b]).abs()/d[2];  
52.      boolean error=false;  
53.      for(int i=0; i<3; i++){  
54.       int p=i;  
55.       int q=(i+1)%3;  
56.       error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;  
57.      }  
58.      if(!error){  
59.       println((a+1)+" "+(b+1)+" "+(c+1));  
60.      }  
61.     }  
62.    }  
63.   }  
64.  }  
65.   
66.  class P{  
67.   double x, y, z;  
68.   
69.   P(){  
70.    this(0, 0, 0);  
71.   }  
72.   
73.   P(double x, double y, double z){  
74.    this.x=x;  
75.    this.y=y;  
76.    this.z=z;  
77.   }  
78.   
79.   P add(P p){  
80.    return new P(x+p.x, y+p.y, z+p.y);  
81.   }  
82.   
83.   P sub(P p){  
84.    return new P(x-p.x, y-p.y, z-p.z);  
85.   }  
86.   
87.   P mul(double m){  
88.    return new P(x*m, y*m, z*m);  
89.   }  
90.   
91.   P div(double d){  
92.    return new P(x/d, y/d, z/d);  
93.   }  
94.   
95.   double abs(){  
96.    return Math.sqrt(abs2());  
97.   }  
98.   
99.   double abs2(){  
100.    return x*x+y*y+z*z;  
101.   }  
102.   
103.   // inner product  
104.   double dot(P p){  
105.    return x*p.x+y*p.y+z*p.y;  
106.   }  
107.   
108.   // outer product  
109.   P det(P p){  
110.    return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);  
111.   }  
112.   
113.   @Override  
114.   public String toString(){  
115.    return x+", "+y+", "+z;  
116.   }  
117.  }  
118.   
119.  void debug(Object... os){  
120.   System.err.println(Arrays.deepToString(os));  
121.  }  
122.   
123.  void print(String s){  
124.   System.out.print(s);  
125.  }  
126.   
127.  void println(String s){  
128.   System.out.println(s);  
129.  }  
130.   
131.  public static void main(String[] args){  
132.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
133.   new Main().run();  
134.  }  
135. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 double[] d;
 P[] ps;
 int n;

 void run(){
  d=new double[3];
  for(int t=sc.nextInt(); t>0; t--){
   for(int i=0; i<3; i++){
    d[i]=sc.nextDouble();
   }
   n=sc.nextInt();
   ps=new P[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double z=sc.nextDouble();
    ps[i]=new P(x, y, z);
   }
   solve();
  }
 }

 void solve(){
  double[] len={0, 0, 0};
  for(int c=0; c<n; c++){
   for(int b=0; b<n; b++){
    if(b==c){
     continue;
    }
    for(int a=0; a<n; a++){
     if(a==b||a==c){
      continue;
     }
     len[0]=ps[b].sub(ps[c]).abs()/d[0];
     len[1]=ps[c].sub(ps[a]).abs()/d[1];
     len[2]=ps[a].sub(ps[b]).abs()/d[2];
     boolean error=false;
     for(int i=0; i<3; i++){
      int p=i;
      int q=(i+1)%3;
      error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;
     }
     if(!error){
      println((a+1)+" "+(b+1)+" "+(c+1));
     }
    }
   }
  }
 }

 class P{
  double x, y, z;

  P(){
   this(0, 0, 0);
  }

  P(double x, double y, double z){
   this.x=x;
   this.y=y;
   this.z=z;
  }

  P add(P p){
   return new P(x+p.x, y+p.y, z+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y, z-p.z);
  }

  P mul(double m){
   return new P(x*m, y*m, z*m);
  }

  P div(double d){
   return new P(x/d, y/d, z/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y+z*z;
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y+z*p.y;
  }

  // outer product
  P det(P p){
   return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
  }

  @Override
  public String toString(){
   return x+", "+y+", "+z;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}