/* Contest : Problem suggestion for SWERC97/98 at Ulm * Problem : Triangle * Method : save free fields to the left * Author : Gerhard Lutz * Date : September 14th, 1997 */ #include #include #include #define N_MAX 500 /* Maximum value of n */ #define DBG(x) FILE* input; int kase=0; int n; /* number of lines per test case */ int best; /* best solution */ char cw[N_MAX][2*N_MAX+10]; /* input triangle */ int l[N_MAX][2*N_MAX+10]; /* number of white fields to the left of each field */ int read_case() { int i; fscanf(input,"%d ",&n); if (n==0) return 0; for (i=0;i1 && cw[r1][c1-1]=='-' && cw[r1][c1-2]=='-') /* always look two fields back */ l[r1][c1]=l[r1][c1-2]+1; else /* the field itself */ l[r1][c1]=1; best=0; /* for each field where new best solution is possible */ for (r1=0;r1=2*best;c1--) /* column from right to left */ { /* calculate biggest triangle where the field is its right edge */ for (r2=1;l[r1][c1]>best && l[r1][c1]-r2>0;r2++) { /* check if the triangle goes to top or bottom */ delta_r = (c1%2==0) ? r2 : -r2; delta_c = (c1%2==0) ? 2*r2 : 0; if (r1+delta_r<0) /* triangle goes to top and out of the * input triangle */ l[r1][c1]=r2; else if (l[r1+delta_r][c1-delta_c]+r2best) best=l[r1][c1]; } /* the solution is the square of 'best' * (sum of odd numbers from 1 to 'best') */ printf("The largest triangle area is %d.\n\n",best*best); } int main() { input = fopen("triangle.in","r"); if (input==NULL) { printf("Error: can't find input file\n");return 1; } while (read_case()) solve_case(); fclose(input); return 0; }