#include #include #include #include #include #include #include #include #include #include #include const char* inname = "triangle" ".in"; #ifdef TUMTEST #define DBG cerr #else #define DBG if (0) cerr #endif ifstream in(inname); #define out cout FILE* fin; template T min(T a, T b) { return (a < b) ? a : b; } template T max(T a, T b) { return (a > b) ? a : b; } int n; char tri[101][200]; int pos[101]; int mp; int triAtPos(int startx, int starty) { DBG << "checking " << startx << " , " << starty << endl; int x, x2; bool failed; bool up = (startx % 2 == 1); int maxsize; int y = starty; x = startx; if (up) { maxsize = min(y+1, n - (y+1) - (x-1)/2); } else { maxsize = min(n-y, n - y - x/2); } DBG << "maxsize " << maxsize << endl; int size = 0; int rows; for (rows = 1; rows <= maxsize; rows++) { failed = false; for (int col = 0; col < rows-1; col++) { x = starty + (up ? -col : col); assert (x >= 0 || x < n); if (tri[x][pos[x]+2] == '#' || tri[x][pos[x]+1] == '#') { failed = true; break; } pos[x] += 2; } if (failed) break; x = starty + (up ? -(rows-1) : (rows-1)); if (up) { x2 = startx + 2*(rows-1); } else { x2 = startx; } pos[x] = x2; if (tri[x][x2] == '#') { break; } size += 1 + (rows-1)*2; } DBG << "size: " << size << endl; return size; } void search() { int best = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 2*(n-i)-1; j++) { best = max(best, triAtPos(j, i)); } } out << "The largest triangle area is " << best << "." << endl; } bool read() { in >> n; if (n ==0) return false; for (int i = 0; i < n; i++) { for (int j = 0; j < 2*(n-i)-1; j++) { in >> ws >> tri[i][j] >> ws; } } return true; } int myX, myY; int getLineUP(int x, int y) { int i; for (i = 0; i < myY; i++) { if (tri[i][x] != '#' || tri[i][x+1] != '#') { return(i - y); } } } int getLineDown(int x, int y) { int i, xi = x; for (i = myY; i >= 0; i--) { if (tri[xi][i] != '#' || tri[xi + 1] != '#') { return (y - i); } xi += 2; } } int myDim[101][201]; int main() { int cnt = 1; fin = fopen(inname, "r"); while (read()) { /* myX = n * 2; myY = n; int xi, yi; for (xi = 0; xi < myX; xi++) { for (yi = 0; yi < myY; yi++) { if ((xi % 2) == 0) { myDim[yi][xi] = getLineDown(xi, yi); } else { myDim[yi][xi] = getLineUp(xi, yi); } } } int best = INT_MAX; for (xi = 0; xi < myX; xi++) { for (yi = 0; yi < myY; yi++) { int b; b = myDim[yi][xi]; for (xi2 = xi; xi2 < myX; xi2 += 2) { if (b - (xi2 - xi)/2) { b = min(b - , myDim[yi][xi2] - } } } */ out << "Triangle #" << cnt++ << endl; search(); out << endl; } return 0; }