AOJ1212 Mirror Illusion - nanikakaのAOJ航海日誌

概要

1辺が8mの正方形がある。中には幅1mの鏡がN枚あり、水平もしくは鉛直に平行に置かれている。
今、男が正方形内の座標(0.75, 0.25)に居て、(1, 0.5)の座標の方を向いている。このとき、男の目に入る景色は正方形内のどこの座標のものかをcm単位で答えよ。
N <= 144

解法

まず、単位をcmに変換すると整数だけ扱えばよくなります。現在位置は(100, 50)となり、向いている方向ベクトルは(25, 25)となります。方向ベクトルは(1, 1)に直しておきました。
方針は男の視線をシミュレートすることです。
視線の開始位置(x, y)と向きべクトル(dx, dy)を管理していきます。初期値はそれぞれ(x, y)=(100,50), (dx, dy)=(1,1)です。男の視線が鏡にぶつからず、正方形の壁か男自身にぶつかればシミュレートは終わります。視線がぶつかった座標が男の目に入る座標です。
水平方向に置かれている鏡に座標(x', y')でぶつかったとします。このとき、ベクトルの水平方向成分は変わらず、鉛直方向成分が逆になります。よって、(x, y)が(x', y')に、(dx, dy)が(dx, -dy)と更新されます。鉛直方向に置かれた鏡にぶつかった場合も同様です。
視線が鏡にぶつかるかの判定をどうやったかを説明します。水平方向に置かれている鏡にぶつかる場合を考えます。
鏡は(X, Y)と(X+100, Y)を端点として置かれているはずです。視線をtだけ動かして、y座標をYにしてみます。つまり、
Y = y + t*dy
より、
t = (Y-y)/dy
が求まります。このtが負の数になったとき、鏡は自分が向いている方向とは逆方向にあるのでぶつかることはないと分かります。そして、tだけ動かせばこの鏡のいるY座標に一致するのだからxの成分についても考えます。
x' = x + t*dx
このx'がX <= x' <= X+100を満たすと、視線はこの鏡にぶつかることが分かります。鏡の端(XもしくはX+100)とぶつかることは起こらないので、隣同士に並んだ鏡の真ん中と衝突することは考えなくていいです。
鏡が向いている方向に対して重なって並んでいるとこれを満たす鏡が複数枚見つかります。その場合、最も近くの鏡とぶつかるので、求まったtが一番小さかった鏡とぶつかることになります。
鉛直方向の鏡についても同様です。

ソース

import java.util.Scanner;

//Mirror Illusion
public class AOJ1212 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[][][] g = {
				{{0, 0},{0, 800}},
				{{0, 0},{800, 0}},
				{{0, 800},{800, 800}},
				{{800, 0},{800, 800}}
		};
		for(;;){
			int n = sc.nextInt();
			if(n<0)break;
			int px = 75, py = 25, dx = 1, dy = 1;
			int[][][] wall = new int[n+1][2][2];
			wall[0][0][0] = wall[0][1][0] = 75; wall[0][0][1] = wall[0][1][1] = 25;
			for(int i=1;i<=n;i++){
				char ch = sc.next().charAt(0);
				int a = sc.nextInt()*100, b = sc.nextInt()*100;
				if(ch=='x'){
					wall[i][0][0] = a; wall[i][0][1] = b;
					wall[i][1][0] = a+100; wall[i][1][1] = b;
				}
				else{
					wall[i][0][0] = a; wall[i][0][1] = b;
					wall[i][1][0] = a; wall[i][1][1] = b+100;
				}
			}
			for(;;){
				int id = -1, min = 1000;
				for(int i=0;i<=n;i++){
					int x1 = wall[i][0][0], x2 = wall[i][1][0], y1 = wall[i][0][1], y2 = wall[i][1][1];
					if(x1==x2){
						int t = (x1-px)/dx;
						if(t<=0||min<=t)continue;
						int y = py+t*dy;
						if(y1<=y&&y<=y2){
							id = i;
							min = t;
						}
					}
					else{
						int t = (y1-py)/dy;
						if(t<=0||min<=t)continue;
						int x = px+t*dx;
						if(x1<=x&&x<=x2){
							id = i;
							min = t;
						}
					}
				}
				if(id==-1){
					min = 1000;
					for(int i=0;i<4;i++){
						int x1 = g[i][0][0], x2 = g[i][1][0], y1 = g[i][0][1], y2 = g[i][1][1];
						if(x1==x2){
							int t = (x1-px)/dx;
							if(t<=0||min<=t)continue;
							int y = py+t*dy;
							if(y1<=y&&y<=y2)min = t;
						}
						else{
							int t = (y1-py)/dy;
							if(t<=0||min<=t)continue;
							int x = px+t*dx;
							if(x1<=x&&x<=x2)min = t;
						}
					}
					System.out.println((px+min*dx)+" "+(py+min*dy));
					break;
				}
				if(id==0){
					System.out.println("75 25");
					break;
				}
				px+=min*dx; py+=min*dy;
				if(wall[id][0][0]==wall[id][1][0])dx*=-1;
				else dy*=-1;
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1212().run();
	}
}