Rectangle

Zonal Computing Olympiad 2015, 29 Nov 2014
We have a rectangular region that is 100000 units along the Xaxis and 500 units along the Y axis.
We assume that the origin (0, 0) is at the bottomleft corner of this region, so that the topleft corner is at (0, 500), the bottomright at (100000, 0) and the topright corner at (100000, 500). We are also given the coordinates of a set of N points inside this region. The points have only integer coordinates and do not appear along the Xaxis or Y axis.
We would like to draw a rectangle, with its base on the Xaxis, of maximum area within the region such that it does not contain any of the N points in its interior. More specifically, the points may appear on the boundary but cannot be properly inside the rectangle.
For example, if there are 5 points: (1, 4), (2, 3), (3, 2), (5, 1) and (5, 2). Then the rectangle whose bottomleft and topright corners are given by (0,0) and (2,3) is a possibility and its area is 6. Another possibility is the rectangle with bottomleft and topright corners at (3,0) and (5,500) with area 1000. The rectangle with bottomleft at (2, 3) and topright at (100000, 500) is not valid since its base does not lie on the Xaxis. The largest rectangle that meets the requirements in this case is the one with its bottomleft corner at (5,0) and topright at (100000,500) with area 49997500.
Your program should take a description of the N points and output the size of the maximum rectangle satisfying the above property that can be drawn within the 100000 × 500 region.
Input format
The first line contains a single integer N, giving the number of points marked in the region.
This is followed by N lines, each containing two integers separated by a space describing the coordinates of one point.
Output format
Output a single integer giving the area of the largest rectangle that may be drawn with its base on the Xaxis and which does not contain any of the given N points in its interior.
Test data
In both subtasks, the Xcoordinate of each of the N points is in the range 1 to 99999 inclusive, and the Y coordinate of each of the N points is in the range 1 to 499 inclusive.
Subtask 1 (40 marks) : 1 ≤ N ≤ 5000.
Subtask 2 (60 marks) : 1 ≤ N ≤ 100000.
Sample Input
5 1 4 2 3 3 2 5 1 5 2
Sample Output
49997500
Author:  admin3 
Date Added:  3112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions