Skip to content

Instantly share code, notes, and snippets.

@agiamas agiamas/gist:2394505
Created Apr 15, 2012

Embed
What would you like to do?
mystic. google code jam 2012. Nice clean solution code.
package gcj;
import com.sun.org.apache.xerces.internal.impl.xs.opti.DefaultXMLDocumentHandler;
import java.util.*;
import java.io.*;
public class HallOfMirrors {
final static String PROBLEM_NAME = "mirrors";
final static String WORK_DIR = "D:\\Gcj\\" + PROBLEM_NAME + "\\";
int H, W, D;
double stX, stY;
int res = 0;
String[] map;
int gcd(int a, int b) {
while (a>0 && b>0)
if (a>b) a %= b; else b %= a;
return a + b;
}
final double EPS = 1e-10;
double getT(double cur, int V) {
cur *= 2; V *= 2;
if (V == 0)
return 1e100;
if (V > 0) {
double want = Math.ceil(cur + EPS);
return (want - cur) / V;
} else {
double want = Math.floor(cur - EPS);
return (want - cur) / V;
}
}
boolean isInteger(double x) {
return Math.abs(x - Math.floor(x)) <= EPS || Math.abs(x - Math.ceil(x)) <= EPS;
}
boolean inMirror(double x, double y) {
int xx = (int)Math.floor(x);
int yy = (int)Math.floor(y);
return map[xx].charAt(yy) == '#';
}
void process(int dx, int dy) {
double curX = stX, curY = stY;
double dist = 0.0;
while (true) {
double t1 = getT(curX, dx);
double t2 = getT(curY, dy);
double t = Math.min(t1, t2);
double nextX = curX + t * dx;
double nextY = curY + t * dy;
double piece = Math.sqrt((nextX - curX) * (nextX - curX) + (nextY - curY) * (nextY - curY));
dist += piece;
if (dist > D + EPS)
return;
if (Math.abs(nextX - stX) <= EPS && Math.abs(nextY - stY) <= EPS) {
res++;
return;
}
curX = nextX;
curY = nextY;
boolean fx = isInteger(nextX);
boolean fy = isInteger(nextY);
if (fx && fy) {
// corner
// A B
// C D
boolean A = inMirror(nextX - EPS, nextY - EPS);
boolean B = inMirror(nextX - EPS, nextY + EPS);
boolean C = inMirror(nextX + EPS, nextY - EPS);
boolean D = inMirror(nextX + EPS, nextY + EPS);
int cnt = (A ? 1 : 0) + (B ? 1 : 0) + (C ? 1 : 0) + (D ? 1 : 0);
if (cnt == 3) {
dx = -dx;
dy = -dy;
} else if (A && B && !C && !D || !A && !B && C & D) {
dx = -dx;
} else if (A && C && !B && !D || !A && !C && B && D) {
dy = -dy;
} else if (inMirror(nextX + (dx > 0 ? EPS : -EPS), nextY + (dy > 0 ? EPS : -EPS))) {
return;
} else {
// just continue;
}
} else if (fx && !fy) {
// horizontal
if (dx != 0 && inMirror(nextX + (dx > 0 ? EPS : -EPS), nextY))
dx = -dx;
} else if (!fx && fy) {
// vertical
if (dy != 0 && inMirror(nextX, nextY + (dy > 0 ? EPS : -EPS)))
dy = -dy;
} else {
// nothing
}
}
}
void solve(Scanner sc, PrintWriter pw) {
H = sc.nextInt();
W = sc.nextInt();
D = sc.nextInt();
map = new String[H];
for (int i=0; i<H; i++)
map[i] = sc.next();
for (int i=0; i<H; i++)
for (int j=0; j<W; j++)
if (map[i].charAt(j) == 'X') {
stX = i + 0.5;
stY = j + 0.5;
}
for (int dx=-D; dx<=D; dx++)
for (int dy=-D; dy<=D; dy++)
if (dx*dx + dy*dy > 0 && dx*dx + dy*dy <= D * D && gcd(Math.abs(dx), Math.abs(dy)) == 1) {
process(dx, dy);
}
pw.println(res);
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new FileReader(WORK_DIR + "input.txt"));
PrintWriter pw = new PrintWriter(new FileWriter(WORK_DIR + "output.txt"));
int caseCnt = sc.nextInt();
for (int caseNum=0; caseNum<caseCnt; caseNum++) {
System.out.println("Processing test case " + (caseNum + 1));
pw.print("Case #" + (caseNum+1) + ": ");
new HallOfMirrors().solve(sc, pw);
}
pw.flush();
pw.close();
sc.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.