| ||||
|
На главную
.............. Задачи .............. Финальная статистика .............. Общая статистика .............. Правила .............. 
|
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");
}
}
}
|
|||
| ||||