#include #define NMAX 40000 int main(void) { int n, h, w; int ss; // stack size int sh[NMAX + 2], end[NMAX + 2]; // height and endpoint of stack rectangles; sentinels at both ends long long maxArea = 0; FILE *f = fopen("skyline.in", "rt"); fscanf(f, "%d", &n); sh[0] = end[0] = 0; ss = 1; for (int i = 0; i <= n ; i++) { // Force a 0-height rectangle at the end to empty the stack. if (i == n) { h = w = 0; } else { fscanf(f, "%d %d", &h, &w); } // Pop taller rectangles from the stack. // Their left coordinate is the endpoint of the previous rectangle on the stack. // Their right coordinate is the endpoint of the top of the stack. int endpoint = end[ss - 1]; while (sh[ss - 1] > h) { long long area = (long long)sh[ss - 1] * (endpoint - end[ss - 2]); if (area > maxArea) { maxArea = area; } // printf("rectangle of height %d starts at %d and ends at %d area %lld\n", sh[ss - 1], end[ss - 2], endpoint, area); ss--; } // Push the new rectangle on the stack. sh[ss] = h; end[ss] = w + endpoint; ss++; } fclose(f); f = fopen("skyline.out", "w"); fprintf(f, "%lld\n", maxArea); fclose(f); }