PKU2725

解けたよー > 薊野氏
入力の最初のパートに出てきたマークの中で
位置がわからないものを一個ずつ動かしてみるDQNアルゴリズム。

import java.io.*;
import java.util.*;

class Main{
	static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] argv) throws Exception{
		for(String s; !(s=r.readLine()).equals("END"); ){
			new Main(s);
		}
	}

	Point[] ps = new Point[26];
	Instruction[] insts = new Instruction[26];
	int target;

	Main(String s) throws Exception{
		String[] ss = s.split(" +");
		while(true){
			if(ss.length == 1){
				ps[getMark(ss[0])] = new Point(-1,-1);
			}
			else if(ss.length == 3){
				ps[getMark(ss[0])] = new Point
					(Integer.parseInt(ss[1]), Integer.parseInt(ss[2]));
			}
			else{break;}
			s = r.readLine();
			ss = s.split(" +");
		}
		while(ss.length == 4){
			insts[getMark(ss[3])] = new Instruction
				(getMark(ss[1]), getMark(ss[2]), ss[0].charAt(0));
			s = r.readLine();
			ss = s.split(" +");
		}
		target = getMark(ss[0]);
		solve();
		if(ps[target] == null){
			System.out.print("UNCERTAIN!\n");
		}
		else{
			System.out.printf("%.2f %.2f\n", ps[target].x, ps[target].y);
		}
	}

	private void solve(){
		Point ans = getPoint(target);
		for(int i=0; i<26; i++){
			if(insts[i] != null || ps[i] == null || ps[i].x >= 0){continue;}

			for(int j=0; j<26; j++){
				if(insts[j] != null){ps[j] = null;}
			}
			ps[i].x = -100;
			if(!getPoint(target).equals(ans)){
				ps[target] = null;
				return;
			}
			ps[i].x = -1;
		}
		ps[target] = ans;
	}

	private Point getPoint(int mark){
		final int MIDDLE = '1', LEFT = '2', RIGHT = '3';
		if(ps[mark] != null){return new Point(ps[mark].x, ps[mark].y);}
		Instruction inst = insts[mark];
		Point p1 = getPoint(inst.mark1);
		Point p2 = getPoint(inst.mark2);
		Point ret;
		if(inst.kind == MIDDLE){
			ret = new Point((p1.x+p2.x)/2, (p1.y+p2.y)/2);
		}
		else if(inst.kind == LEFT){
			ret = new Point(p2.x - p2.y + p1.y, p2.y + p2.x - p1.x);
		}
		else{
			ret = new Point(p2.x + p2.y - p1.y, p2.y - p2.x + p1.x);
		}
		return ps[mark] = ret;
	}

	private static int getMark(String s){
		return s.charAt(0) - 'A';
	}
}

class Point{
	double x, y;
	Point(double x_, double y_){
		x = x_;
		y = y_;
	}
	public boolean equals(Object o){
		final double EPS = 1e-6;
		Point p = (Point)o;
		return ((x==0&&p.x==0) || Math.abs(1 - x/p.x) < EPS) &&
			((y==0&&p.y==0) || Math.abs(1 - y/p.y) < EPS);
	}
}

class Instruction{
	int mark1, mark2, kind;
	Instruction(int m1, int m2, int k){
		mark1 = m1;
		mark2 = m2;
		kind = k;
	}
}