Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

回転および平行移動を適用したということは，各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる．従って，元の折れ線の内の1つの線分ベクトルと，探す対象の折れ線の内の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.  int n;  
17.  int[] m;  
18.  int[][] xs, ys;  
19.   
20.  void run(){  
21.   for(;;){  
22.    n=sc.nextInt();  
23.    if(n==0){  
24.     break;  
25.    }  
26.    m=new int[n+1];  
27.    xs=new int[n+1][];  
28.    ys=new int[n+1][];  
29.    for(int j=0; j<=n; j++){  
30.     m[j]=sc.nextInt();  
31.     xs[j]=new int[m[j]];  
32.     ys[j]=new int[m[j]];  
33.     for(int i=0; i<m[j]; i++){  
34.      xs[j][i]=sc.nextInt();  
35.      ys[j][i]=sc.nextInt();  
36.     }  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   for(int i=1; i<=n; i++){  
44.    if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){  
45.     println(i+"");  
46.    }  
47.   }  
48.   println("+++++");  
49.  }  
50.   
51.  boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){  
52.   int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},  
53.     {{0, 1}, {-1, 0}}};  
54.   
55.   int k1=-1, k2=-1;  
56.   for(int j=0; j<4; j++){  
57.    int vx1=xs1[1]-xs1[0];  
58.    int vy1=ys1[1]-ys1[0];  
59.    int vx2=xs2[1]-xs2[0];  
60.    int vy2=ys2[1]-ys2[0];  
61.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2  
62.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){  
63.     k1=j;  
64.    }  
65.    int vx3=xs2[m-2]-xs2[m-1];  
66.    int vy3=ys2[m-2]-ys2[m-1];  
67.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3  
68.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){  
69.     k2=j;  
70.    }  
71.   }  
72.   
73.   boolean f1=k1!=-1, f2=k2!=-1;  
74.   for(int i=0; i<m-1; i++){  
75.    int vx1=xs1[i+1]-xs1[i];  
76.    int vy1=ys1[i+1]-ys1[i];  
77.    int vx2=xs2[i+1]-xs2[i];  
78.    int vy2=ys2[i+1]-ys2[i];  
79.    int vx3=xs2[m-i-2]-xs2[m-i-1];  
80.    int vy3=ys2[m-i-2]-ys2[m-i-1];  
81.    if(k1!=-1){  
82.     f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2  
83.       &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;  
84.    }  
85.    if(k2!=-1){  
86.     f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3  
87.       &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;  
88.    }  
89.   }  
90.   
91.   return f1||f2;  
92.  }  
93.   
94.  void debug(Object... os){  
95.   System.err.println(Arrays.deepToString(os));  
96.  }  
97.   
98.  void print(String s){  
99.   System.out.print(s);  
100.  }  
101.   
102.  void println(String s){  
103.   System.out.println(s);  
104.  }  
105.   
106.  public static void main(String[] args){  
107.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
108.   new Main().run();  
109.  }  
110. }  

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;

 int n;
 int[] m;
 int[][] xs, ys;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=new int[n+1];
   xs=new int[n+1][];
   ys=new int[n+1][];
   for(int j=0; j<=n; j++){
    m[j]=sc.nextInt();
    xs[j]=new int[m[j]];
    ys[j]=new int[m[j]];
    for(int i=0; i<m[j]; i++){
     xs[j][i]=sc.nextInt();
     ys[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  for(int i=1; i<=n; i++){
   if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){
    println(i+"");
   }
  }
  println("+++++");
 }

 boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){
  int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},
    {{0, 1}, {-1, 0}}};

  int k1=-1, k2=-1;
  for(int j=0; j<4; j++){
   int vx1=xs1[1]-xs1[0];
   int vy1=ys1[1]-ys1[0];
   int vx2=xs2[1]-xs2[0];
   int vy2=ys2[1]-ys2[0];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){
    k1=j;
   }
   int vx3=xs2[m-2]-xs2[m-1];
   int vy3=ys2[m-2]-ys2[m-1];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){
    k2=j;
   }
  }

  boolean f1=k1!=-1, f2=k2!=-1;
  for(int i=0; i<m-1; i++){
   int vx1=xs1[i+1]-xs1[i];
   int vy1=ys1[i+1]-ys1[i];
   int vx2=xs2[i+1]-xs2[i];
   int vy2=ys2[i+1]-ys2[i];
   int vx3=xs2[m-i-2]-xs2[m-i-1];
   int vy3=ys2[m-i-2]-ys2[m-i-1];
   if(k1!=-1){
    f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2
      &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;
   }
   if(k2!=-1){
    f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3
      &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;
   }
  }

  return f1||f2;
 }

 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();
 }
}