Colored Paper 3
InterviewTime limit1sMemory limit128 MB
Given up to 100 aligned black 10x10 squares on a 100x100 grid, find the maximum area axis-aligned all-black rectangle.
- Level
Medium5 of 10
- Topics
- Array, Brute force, Matrix
- Solved
- No attempts yet
Problem
A white square paper has width 100 and height 100. Black square papers, each with width 10 and height 10, are attached to it so that every side of a black paper is parallel to a side of the white paper. After attaching one or more black papers, you want to cut out one black rectangle from the white paper. The rectangle must also have all of its sides parallel to the sides of the white paper.
For instance, suppose three black papers are attached as shown in Figure 1. If the black rectangle marked in Figure 1 is cut out, its area is 22×5=110.
On the other hand, if the black rectangle marked in Figure 2 is cut out, its area is 8×15=120.
Given the number of black papers and the position where each one is attached, write a program that finds the maximum possible area of a black rectangle that can be cut out.
Input
The first line contains the number of black papers. From the second line onward, each line contains the position of one black paper. The position is given by two natural numbers. The first number is the distance between the left side of the black paper and the left side of the white paper, and the second number is the distance between the bottom side of the black paper and the bottom side of the white paper. The number of black papers is at most 100, and no black paper extends outside the white paper.
Output
Print the maximum area of a black rectangle that can be cut out.