Aizu Online Judge 1212 Mirror Illusion

■1212 Mirror Illusion

ある座標pから方向vを見ていたとする．ちなみに，初期条件は，p₀=(0.75, 0.25)，v₀=(1, 1)
vのノルムを16以上にとれば，(p+v)が必ず室外に出るので，以下vをそういうベクトルとする．
まず，(p, p+v)が人に当たるかを調べる．当たっていたらそこで終了．
次に，(p, p+v)が鏡に当たるかを調べる． 一つでも当たる鏡があれば，その内で交差点が最もpに近い鏡mを選ぶ．pを，(p, p+v)とmとの交差点とする．また，新しい方向ベクトルを， mが横置きだったらv'=(v_x, -v_y)， 縦置きだったらv'=(-v_x, v_y)とする．
一つも当たらなかった場合は，外壁のいずれかに当たっていることになるので，4つの壁それぞれについて当たっているかおよび交差点を計算．

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.  Seg[] segs;  
19.   
20.  void run(){  
21.   m=8;  
22.   for(;;){  
23.    n=sc.nextInt();  
24.    if(n<0){  
25.     break;  
26.    }  
27.    segs=new Seg[n];  
28.    for(int i=0; i<n; i++){  
29.     char c=sc.next().charAt(0);  
30.     int x=sc.nextInt();  
31.     int y=sc.nextInt();  
32.     if(c=='x'){  
33.      segs[i]=new Seg(0, x, y, x+1, y);  
34.     }else{  
35.      segs[i]=new Seg(1, x, y, x, y+1);  
36.     }  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   P p0=new P(0.75, 0.25);  
44.   P p=new P(0.75, 0.25);  
45.   P v=new P(1, 1);  
46.   Seg[] walls=new Seg[4];  
47.   walls[0]=new Seg(0, 0, 0, m, 0);  
48.   walls[1]=new Seg(0, 0, m, m, m);  
49.   walls[2]=new Seg(0, 0, 0, 0, m);  
50.   walls[3]=new Seg(0, m, 0, m, m);  
51.   
52.   for(int i=0; i<10; i++){  
53.    v=v.div(v.abs()).mul(2*m);  
54.   
55.    if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){  
56.     int x=(int)(p0.x*100+EPS);  
57.     int y=(int)(p0.y*100+EPS);  
58.     println(x+" "+y);  
59.     break;  
60.    }  
61.   
62.    Seg seg=null;  
63.    P p2=null;  
64.    double min=INF;  
65.    for(Seg s : segs){  
66.     if(crsSS(p, p.add(v), s.p1, s.p2)){  
67.      P q=isLL(p, p.add(v), s.p1, s.p2);  
68.      double d=p.sub(q).abs();  
69.      if(d<min+EPS&&d>EPS){  
70.       seg=s;  
71.       p2=q;  
72.       min=p.sub(q).abs();  
73.      }  
74.     }  
75.    }  
76.   
77.    if(p2!=null){  
78.     p=p2;  
79.     if(seg.d==0){  
80.      v.y=-v.y;  
81.     }else{  
82.      v.x=-v.x;  
83.     }  
84.    }else{  
85.     for(Seg s : walls){  
86.      if(crsSS(p, p.add(v), s.p1, s.p2)){  
87.       P q=isLL(p, p.add(v), s.p1, s.p2);  
88.       if(p.sub(q).abs()>EPS){  
89.        int x=(int)(q.x*100+EPS);  
90.        int y=(int)(q.y*100+EPS);  
91.        println(x+" "+y);  
92.       }  
93.      }  
94.     }  
95.     break;  
96.    }  
97.   }  
98.  }  
99.   
100.  // 線分と点の距離  
101.  double disSP(P p1, P p2, P q){  
102.   if(p2.sub(p1).dot(q.sub(p1))<EPS)  
103.    return q.sub(p1).abs();  
104.   if(p1.sub(p2).dot(q.sub(p2))<EPS)  
105.    return q.sub(p2).abs();  
106.   return disLP(p1, p2, q);  
107.  }  
108.   
109.  // 直線と点の距離  
110.  double disLP(P p1, P p2, P q){  
111.   return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();  
112.  }  
113.   
114.  // 線分と線分の交差判定  
115.  boolean crsSS(P p1, P p2, P q1, P q2){  
116.   if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))  
117.    return false;  
118.   if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))  
119.    return false;  
120.   if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))  
121.    return false;  
122.   if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))  
123.    return false;  
124.   return signum(p2.sub(p1).det(q1.sub(p1)))  
125.     *signum(p2.sub(p1).det(q2.sub(p1)))<EPS  
126.     &&signum(q2.sub(q1).det(p1.sub(q1)))  
127.       *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;  
128.  }  
129.   
130.  // 直線と直線の交点  
131.  P isLL(P p1, P p2, P q1, P q2){  
132.   double d=q2.sub(q1).det(p2.sub(p1));  
133.   if(abs(d)<EPS)  
134.    return null;  
135.   return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));  
136.  }  
137.   
138.  class Seg{  
139.   int d;  
140.   P p1, p2;  
141.   
142.   Seg(int d, int x1, int y1, int x2, int y2){  
143.    this.d=d;  
144.    p1=new P(x1, y1);  
145.    p2=new P(x2, y2);  
146.   }  
147.  }  
148.   
149.  // 2 dimensions  
150.  class P{  
151.   double x, y;  
152.   
153.   P(){  
154.    this(0, 0);  
155.   }  
156.   
157.   P(double x, double y){  
158.    this.x=x;  
159.    this.y=y;  
160.   }  
161.   
162.   P add(P p){  
163.    return new P(x+p.x, y+p.y);  
164.   }  
165.   
166.   P sub(P p){  
167.    return new P(x-p.x, y-p.y);  
168.   }  
169.   
170.   P mul(double m){  
171.    return new P(x*m, y*m);  
172.   }  
173.   
174.   P div(double d){  
175.    return new P(x/d, y/d);  
176.   }  
177.   
178.   double abs(){  
179.    return Math.sqrt(abs2());  
180.   }  
181.   
182.   double abs2(){  
183.    return x*x+y*y;  
184.   }  
185.   
186.   double arg(){  
187.    return Math.atan2(y, x);  
188.   }  
189.   
190.   // inner product  
191.   double dot(P p){  
192.    return x*p.x+y*p.y;  
193.   }  
194.   
195.   // outer product  
196.   double det(P p){  
197.    return x*p.y-y*p.x;  
198.   }  
199.   
200.   P rot90(){  
201.    return new P(-y, x);  
202.   }  
203.   
204.   // conjugation  
205.   P conj(){  
206.    return new P(x, -y);  
207.   }  
208.  }  
209.   
210.  void debug(Object... os){  
211.   System.err.println(Arrays.deepToString(os));  
212.  }  
213.   
214.  void print(String s){  
215.   System.out.print(s);  
216.  }  
217.   
218.  void println(String s){  
219.   System.out.println(s);  
220.  }  
221.   
222.  public static void main(String[] args){  
223.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
224.   new Main().run();  
225.  }  
226. }  

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;
 Seg[] segs;

 void run(){
  m=8;
  for(;;){
   n=sc.nextInt();
   if(n<0){
    break;
   }
   segs=new Seg[n];
   for(int i=0; i<n; i++){
    char c=sc.next().charAt(0);
    int x=sc.nextInt();
    int y=sc.nextInt();
    if(c=='x'){
     segs[i]=new Seg(0, x, y, x+1, y);
    }else{
     segs[i]=new Seg(1, x, y, x, y+1);
    }
   }
   solve();
  }
 }

 void solve(){
  P p0=new P(0.75, 0.25);
  P p=new P(0.75, 0.25);
  P v=new P(1, 1);
  Seg[] walls=new Seg[4];
  walls[0]=new Seg(0, 0, 0, m, 0);
  walls[1]=new Seg(0, 0, m, m, m);
  walls[2]=new Seg(0, 0, 0, 0, m);
  walls[3]=new Seg(0, m, 0, m, m);

  for(int i=0; i<10; i++){
   v=v.div(v.abs()).mul(2*m);

   if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){
    int x=(int)(p0.x*100+EPS);
    int y=(int)(p0.y*100+EPS);
    println(x+" "+y);
    break;
   }

   Seg seg=null;
   P p2=null;
   double min=INF;
   for(Seg s : segs){
    if(crsSS(p, p.add(v), s.p1, s.p2)){
     P q=isLL(p, p.add(v), s.p1, s.p2);
     double d=p.sub(q).abs();
     if(d<min+EPS&&d>EPS){
      seg=s;
      p2=q;
      min=p.sub(q).abs();
     }
    }
   }

   if(p2!=null){
    p=p2;
    if(seg.d==0){
     v.y=-v.y;
    }else{
     v.x=-v.x;
    }
   }else{
    for(Seg s : walls){
     if(crsSS(p, p.add(v), s.p1, s.p2)){
      P q=isLL(p, p.add(v), s.p1, s.p2);
      if(p.sub(q).abs()>EPS){
       int x=(int)(q.x*100+EPS);
       int y=(int)(q.y*100+EPS);
       println(x+" "+y);
      }
     }
    }
    break;
   }
  }
 }

 // 線分と点の距離
 double disSP(P p1, P p2, P q){
  if(p2.sub(p1).dot(q.sub(p1))<EPS)
   return q.sub(p1).abs();
  if(p1.sub(p2).dot(q.sub(p2))<EPS)
   return q.sub(p2).abs();
  return disLP(p1, p2, q);
 }

 // 直線と点の距離
 double disLP(P p1, P p2, P q){
  return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();
 }

 // 線分と線分の交差判定
 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class Seg{
  int d;
  P p1, p2;

  Seg(int d, int x1, int y1, int x2, int y2){
   this.d=d;
   p1=new P(x1, y1);
   p2=new P(x2, y2);
  }
 }

 // 2 dimensions
 class P{
  double x, y;

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

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

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

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

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

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

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

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

  double arg(){
   return Math.atan2(y, x);
  }

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

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

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }
 }

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