| ||||
import java.io.*; import java.util.*; public class Main implements Runnable { final private boolean DEBUG = false; final private double small = 0.0396; class point { double x, y; point(double X, double Y) { x = X; y = Y; } } class compareY implements Comparator<point>{ public int compare(point a, point b) { if(a.y == b.y)return (int)(a.x - b.x); return (a.y < b.y)?-1:1; } } class compareX implements Comparator<point>{ public int compare(point a, point b) { if(a.x == b.x)return (int)(a.y - b.y); return (a.x < b.x)?-1:1; } } int all = 0; ArrayList<point> c; double xmin, xmax, ymin, ymax; double p2 = 0.5000, p3 = 0.3333, p4 = 0.25000, p5 = 0.20000, p6 = 0.1666667; double p8 = p4 * 0.5000, p16 = p8 * 0.50000; PrintWriter cout; ArrayList<Integer> right; double EPS = 0.04, Amin = -Math.PI / 3, Amax = Math.PI / 3; char checkOneLetter(ArrayList<point> a){ ++all; xmin = Collections.min(a, new compareX()).x; xmax= Collections.max(a, new compareX()).x; ymin = Collections.min(a, new compareY()).y; ymax= Collections.max(a, new compareY()).y; for(int i = 0; i < a.size();i++){ point p = a.get(i); p.x -= xmin; p.y -= ymin; p.x /= (xmax - xmin); p.y /= (ymax - ymin); a.set(i, p); } if(DEBUG){ printLetter(a); } char res = ' '; double[] p = new double[8]; p[0] = Math.min(distTo(new point(1, p2), a), distTo(new point(1 - p16, p2), a)); if(Math.abs(p[0]) < small){ // part 1 p[1] = Math.min(Math.min(distTo(new point(p2, p2), a), distTo(new point(p2, p2 + p16), a)), Math.min(distTo(new point(p2 + p16, p2), a), distTo(new point(p2 - p16, p2), a))); if (Math.abs(p[1]) < small){ // part 3 p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16 / 2, 1 - p16), a)); if(Math.abs(p[2]) < small){ // part 7 p[3] = distTo(new point(3 * p4, p2), a); if(Math.abs(p[3]) < small){ return (checkI(a) < checkM(a))?'I':'M'; }else{ p[4] = distTo(new point(p2, p4), a); if(Math.abs(p[4]) < small){ return (checkE(a) < checkB(a))?'E':'B'; }else{ return 'Z'; } } }else{ // part 8 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 16 p[4] = distTo(new point(p2, p5), a); if(Math.abs(p[4]) < small){ return (checkF(a) < checkM(a))?'F':'M'; }else{ p[5] = distTo(new point(EPS, p2), a); if(Math.abs(p[5]) < small){ p[6] = Math.min(distTo(new point(0, 0), a), distTo(new point(EPS, p16), a)); if(Math.abs(p[6]) < small){ return 'T'; }else{ p[7] = Math.min(distTo(new point(p8, p8), a), distTo(new point(p8 + EPS, p8 + p16), a)); return (Math.abs(p[7]) < small)?'G':'J'; } }else{ return 'Y'; } } }else{ // part 17 double best = checkI(a); res = 'I'; double s = checkB(a); if(s < best){ best = s; res = 'B'; } s = checkE(a); if(s < best){ best = s; res = 'E'; } s = checkG(a); if(s < best){ best = s; res = 'G'; } s = checkP(a); if(s < best){ best = s; res = 'P'; } s = checkS(a); if(s < best){ best = s; res = 'S'; } } } }else { // part 4 p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - 16, 1 - 16), a)); if(Math.abs(p[2]) < small){ // part 9 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 18 return 'M'; }else{ // part 19 p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(p16, p16), a)); return (Math.abs(p[4]) < small)?'L':'Q'; } }else{ // part 10 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 20 p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(p16, p16), a)); if(Math.abs(p[4]) < small){ // UV p[5] = distTo(new point(p2, p4), a); return (Math.abs(p[5]) < small)?'V':'U'; }else{ // CJ p[5] = distTo(new point(p2 - Math.sqrt(2.0) / 4.0, p2 - Math.sqrt(2.0) / 4.0), a); return (Math.abs(p[5]) < small)?'C':'J'; } }else{ // part 21 p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(EPS, p16), a)); if(Math.abs(p[4]) < small){ p[5] = distTo(new point(p2, 1 - p16), a); return (Math.abs(p[5]) < small)?'D':'L'; }else{ // OCG Qc p[5] = distTo(new point(p2, 1 - p8), a); if(Math.abs(p[5]) < small){ // OG Q // here should be dfs for filled region by O !!! p[6] = distTo(new point(1.0 - p5, p2), a); if(Math.abs(p[6]) < small){ return 'Q'; }else{ p[7] = Math.min(distTo(new point(2 * p3, p2), a), distTo(new point(p2, 2 * p3), a)); return (Math.abs(p[7]) < small)?'G':'O'; } }else{ return 'C'; } } } } } }else{ // part 2 p[1] = Math.min(Math.min(distTo(new point(p2, p2), a), distTo(new point(p2 - p16, p2), a)), distTo(new point(p2, p2 - p16), a)); if (Math.abs(p[1]) < small){ // part 5 p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16, 1 - p16), a)); if(Math.abs(p[2]) < small){ // part 11 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 22 p[4] = Math.min(distTo(new point(p2, 0), a), Math.min(distTo(new point(p2, p8), a), distTo(new point(p2, p4), a))); if(Math.abs(p[4]) < small){ // KNH M p[5] = Math.min(distTo(new point(p2, 1), a), Math.min(distTo(new point(p2, 1 - p8), a), distTo(new point(p2, 1 - p4), a))); if(Math.abs(p[5]) < small){ p[6] = distTo(new point(p4, p2 + p8), a); if(Math.abs(p[6]) < small){ return 'M'; }else{ return (checkH(a) < checkN(a))?'H':'N'; } }else{ return 'K'; } }else{ // X return 'X'; } }else{ // part 23 p[4] = distTo(new point(p16, p2), a); return (Math.abs(p[4]) < small)?'R':'K'; } }else{ // part 12 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 24 p[4] = distTo(new point(p2, 1 - p16), a); if(Math.abs(p[4]) >= small){ // F W p[5] = distTo(new point(1 - p16, p16), a); return (Math.abs(p[5]) < small)?'F':'W'; }else{ p[5] = distTo(new point(3 * p4, 3 * p8), a); return (Math.abs(p[5]) < small)?'W':'N'; } }else{ // part 25 return 'P'; } } }else { // part 6 p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16, 1 - p16), a)); if(Math.abs(p[2]) < small){ // part 13 p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a)); if(Math.abs(p[3]) < small){ // part 26 return 'M'; }else{ // part 27 p[4] = Math.min(distTo(new point(1, 0), a), distTo(new point(1 - EPS, EPS), a)); return (Math.abs(p[4]) < small)?'A':'Q'; } }else{ // part 14 return 'W'; } } } return res; } ArrayList<point> trans(ArrayList<point> a, double fi){ ArrayList<point> res = new ArrayList<point>(); for (point p: a) { res.add(new point(p.x * Math.cos(fi) + p.y * Math.sin(fi), p.y * Math.cos(fi) - p.x * Math.sin(fi))); } return res; } double fun(double Q) { ArrayList<point> t = trans(XY, Q); double xmax = Collections.max(t, new compareX()).x; double xmin = Collections.min(t, new compareX()).x; return xmax - xmin; } double CalcRo() { double minv = 1E+20; double l = Amin, r = Amax; double a = l, b = r; double coef = 0.8600; int iter = 6; double minp = l; while (Math.abs(r - l) > EPS) { double c = l; double step = (r - l) / iter; for (int i = 0; i <= iter; i++) { double temp = fun(c); if (temp < minv) { minv = temp; minp = c; } c += step; } double wi = (r - l) * coef / 2.0; l = minp - wi; r = minp + wi; if (l < a) { l = a; r = a + wi * 2.0; } if (r > b) { r = b; l = b - wi * 2.0; } coef -= 0.01; if (coef < 0.54) coef = 0.54; } return minp; } public static void main(String[] args) throws Exception { Main solve = new Main(); solve.run(); } String[] map; void run2()throws Exception { BufferedReader cin; StringTokenizer sto = null; if(DEBUG){ cin = new BufferedReader(new FileReader("input.txt")); cout = new PrintWriter("output.txt"); }else{ cout = new PrintWriter(System.out); cin = new BufferedReader(new InputStreamReader(System.in)); } int tests = Integer.parseInt(cin.readLine()); for(int t = 0; t < tests; t++){ map = new String[200]; for (int i = 0; i < map.length; i++) { if(sto == null || !sto.hasMoreTokens()) sto = new StringTokenizer(cin.readLine()); map[i] = sto.nextToken(); } goEating(); } cout.close(); } boolean[][] used; ArrayList<point> cur; ArrayList<point> xy, XY; int k; private void goEating() { used = new boolean[200][200]; right = new ArrayList<Integer>(); xy = new ArrayList<point>(); XY = new ArrayList<point>(); for (int j = 0; j < 200; j++){ for(int i = 0; i < 200; i++){ if(used[i][j] || map[i].charAt(j) == '.'){ continue; } k = 0; cur = new ArrayList<point>(); dfs(i, j); if(k < 15){ continue; } xy.addAll(cur); right.add(xy.size() - 1); } } // //cout.println(XY.size()); double angle = CalcRo(); // if (DEBUG){ cout.println(angle/Math.PI * 180); } // for(int i = 0; i < xy.size(); i++){ point p = xy.get(i); p = new point(p.x * Math.cos(angle) + p.y * Math.sin(angle), p.y * Math.cos(angle) - p.x * Math.sin(angle)); xy.set(i, p); } // int st = 0; for(int i : right){ cur = new ArrayList<point>(); for(int j = st; j <= i; j++){ cur.add(new point(xy.get(j).x, xy.get(j).y)); } st = i + 1; cout.print(checkOneLetter(cur)); } cout.println(); } int[] dx = {0, 0, -1, 1, 1, -1, 1, -1}; int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1}; private int sosed(int i , int j){ int res = 0; res += (i + 1 < 200 && map[i + 1].charAt(j) == 'X')?1:0; res += (j + 1 < 200 && map[i].charAt(j + 1) == 'X')?1:0; res += (i - 1 > -1 && map[i - 1].charAt(j) == 'X')?1:0; res += (j - 1 > -1 && map[i].charAt(j - 1) == 'X')?1:0; return res; } private void dfs(int i, int j) { used[i][j] = true; ++k; if(sosed(i, j) >= 2){ cur.add(new point(i, j)); if(cur.size() % 12 == 7){ XY.add(cur.get(cur.size() - 1)); } } int nx, ny; for(int dir = 0; dir < 4; dir++){ nx = dx[dir] + i; ny = dy[dir] + j; if(nx < 0 || ny < 0 || nx >= 200 || ny >= 200 || used[nx][ny] || map[nx].charAt(ny) == '.'){ continue; } dfs(nx, ny); } } // void printLetter(ArrayList<point> a){ int C = 20; boolean[][] pic = new boolean[C+1][C+1]; for(point p : a){ pic[(int)(p.x * C)][(int)(p.y * C)] = true; } for(int i = 0; i <= C; i++){ for(int j = 0;j <= C; j++){ cout.print(pic[i][j]?'X':'.'); } cout.println(); } cout.println(); } double distTo(point p, ArrayList<point> a){ double res = Double.MAX_VALUE; for(point q : a){ res = Math.min(res, Math.hypot(p.x - q.x, p.y - q.y)); } return res; } // double difference(ArrayList<point> a){ double ret = 0, last = 0; for(point p: c){ double min = 1E+20; for(point q: a){ min = Math.min(min, Math.hypot(p.x - q.x, p.y - q.y)); } last = min; ret += min; } ret += p2 - last * 2; return ret / (1.0 * c.size()); } private double checkG(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(EPS, 1 - EPS)); c.add(new point(EPS, p2)); c.add(new point(p4, p8)); c.add(new point(p2, 0)); c.add(new point(p2, 2 * p3)); c.add(new point(1 - p16, 3 * p8)); c.add(new point(1.000 - EPS, p2)); c.add(new point(1 - p16, 5 * p8)); // c.add(new point(p2, p3)); return difference(a); } private double checkS(ArrayList<point> a) { c = new ArrayList<point>(); // //c.add(new point(EPS, 1 - EPS)); c.add(new point(p16, p2)); c.add(new point(p4, EPS)); c.add(new point(p8, p5)); c.add(new point(p2, p4)); c.add(new point(p2, p2)); c.add(new point(p2, 3.0 * p4)); c.add(new point(3 * p4, 1 - p16)); c.add(new point(1.000 - p16, p16)); //c.add(new point(1.0 - p16, 0.0)); // c.add(new point(p2 - p8, 1)); return difference(a); } // private double checkA(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, p2)); c.add(new point(p4, 3.0 * p8)); c.add(new point(p4, 5.0 * p8)); c.add(new point(2 * p3, 1.0 * p4)); c.add(new point(2 * p3, 3.0 * p4)); c.add(new point(2 * p3, p2)); c.add(new point(3 * p4, 1.0 * p8)); c.add(new point(3 * p4, 7.0 * p8)); c.add(new point(1.000, 0)); c.add(new point(1.0, 1.0)); // c.add(new point(0, 1)); return difference(a); } // private double checkB(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(p16, p16)); c.add(new point(p16, 3 * p4)); c.add(new point(p4, p8)); c.add(new point(p4, 1.0 - EPS)); c.add(new point(p2, p16)); c.add(new point(p2, 3 * p4)); c.add(new point(3 * p4, p16)); c.add(new point(3 * p4, 1 - p16)); c.add(new point(1.00 - EPS, 0)); c.add(new point(1.00 - EPS, 3 * p4)); // c.add(new point(3 * p4, p2)); return difference(a); } // private double checkE(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, p2)); c.add(new point(0, 1)); c.add(new point(p2, 0.0)); c.add(new point(p2, p2)); c.add(new point(p2, 1)); c.add(new point(1, 0)); c.add(new point(1, p2)); c.add(new point(1.00, 3 * p4)); c.add(new point(1.0, 1)); // c.add(new point(3 * p4, 1)); return difference(a); } // private double checkF(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, p2)); c.add(new point(0, 1)); c.add(new point(p4, 0.0)); c.add(new point(p2, 0)); c.add(new point(p2, p3)); c.add(new point(p2, 2 * p3)); c.add(new point(p2, 3 * p4)); c.add(new point(3 * p4, 0)); c.add(new point(1.0, 0)); // c.add(new point(1, 1)); return difference(a); } // private double checkP(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, p2)); c.add(new point(p4, 1.0)); c.add(new point(p4, 1.0)); c.add(new point(p4, p16)); c.add(new point(0, p4)); c.add(new point(p2, p2)); c.add(new point(p2, 3 * p4)); c.add(new point(3 * p4, p16)); c.add(new point(1.0, p16)); // c.add(new point(3 * p4, 1)); return difference(a); } // private double checkH(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, p16)); c.add(new point(0, 1 - p16)); c.add(new point(p2, 2 * p3)); c.add(new point(p2, p3)); c.add(new point(p2, p2)); c.add(new point(1.00 - p16, p16)); c.add(new point(1.00 - p16, 1)); // c.add(new point(p4, p2)); return difference(a); } // private double checkN(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, p16)); c.add(new point(0, 1 - p16)); c.add(new point(p5, p5)); c.add(new point(4 * p5, 4 * p5)); c.add(new point(1 - p16, 1 - p16)); c.add(new point(p2, EPS)); c.add(new point(p2, 1)); c.add(new point(1.00, p16)); // c.add(new point(p4, p5)); return difference(a); } // private double checkI(ArrayList<point> a) { double s1; c = new ArrayList<point>(); // //c.add(new point(0, 3 * p8)); c.add(new point(p4, p2)); //c.add(new point(0, 5 * p8)); c.add(new point(p4, p2)); c.add(new point(p2, p2)); c.add(new point(3 * p4, p2)); //c.add(new point(1, 3 * p8)); c.add(new point(1, p4)); c.add(new point(1.00, p2)); //c.add(new point(1.00, 5 * p8)); // c.add(new point(p2, 0)); s1 = difference(a); return s1; } // private double checkT(ArrayList<point> a) { double s1; c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, p4)); c.add(new point(0, p2)); c.add(new point(0, 3 * p4)); c.add(new point(0, 1)); c.add(new point(p5, p2)); c.add(new point(2 * p5, p2)); c.add(new point(3 * p5, p2)); c.add(new point(4 * p5, p2)); c.add(new point(1.00, p2)); // c.add(new point(2 * p3, 1)); s1 = difference(a); return s1; } // private double checkK(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, 1)); c.add(new point(p4, 0.0)); c.add(new point(p4, p2)); c.add(new point(p2, 0)); c.add(new point(4 * p6, p3)); c.add(new point(5 * p6, 2 * p3)); c.add(new point(p4, 0)); c.add(new point(1.00, 0)); c.add(new point(1.00, 1)); // c.add(new point(p2, 1)); return difference(a); } // private double checkL(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(p5, 0)); c.add(new point(2 * p5, 0)); c.add(new point(3 * p5, 0)); c.add(new point(4 * p5, 0)); c.add(new point(1, 0)); c.add(new point(1, 1)); c.add(new point(1, p4)); c.add(new point(1.00, p2)); c.add(new point(1.00, 3 * p4)); // c.add(new point(p2, p2)); return difference(a); } // private double checkM(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, p8)); c.add(new point(0, 1 - p8)); c.add(new point(p2, p3)); c.add(new point(p2, 2 * p3)); c.add(new point(3 * p5, p8)); c.add(new point(3 * p5, 1 - p8)); c.add(new point(1, p8)); c.add(new point(1, 1 - p8)); c.add(new point(1.00 - p5 / 2, p2 - p16)); c.add(new point(1.00 - p5 / 2, p2 + p16)); // c.add(new point(0, p2)); return difference(a); } // private double checkV(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, 0)); c.add(new point(0, 1)); c.add(new point(p4, p8)); c.add(new point(p2, p4)); c.add(new point(3 * p4, 3 * p8)); c.add(new point(1, p2)); c.add(new point(1, p2)); c.add(new point(3 * p4, 5 * p8)); c.add(new point(p2, 3 * p4)); c.add(new point(p4, 7 * p8)); // c.add(new point(p3, p2)); return difference(a); } // private double checkW(ArrayList<point> a) { c = new ArrayList<point>(); // c.add(new point(0, p16)); c.add(new point(0, 1 - p16)); c.add(new point(p5 / 2, p2 - p16)); c.add(new point(p5 / 2, p2 + p16)); c.add(new point(p2, p8)); c.add(new point(p2, 3 * p8)); c.add(new point(p2, 5 * p8)); c.add(new point(p2, 7 * p8)); c.add(new point(1, p4)); c.add(new point(1, 3 * p4)); // c.add(new point(1, p2)); return difference(a); } public void run() { try { run2(); } catch (Exception e) { e.printStackTrace(); throw new RuntimeException("dfgfg"); } } } |
||||
|