2426. Maximum Rectangle Window

单点时限: 3.0 sec

内存限制: 256 MB

You are a staff of the hotel ICPC(Inter-Continental Private Comfort) person in charge of a plan to open a new hotel by renovating a old house for sale.

But there is one problem for the plan. Windows in this house have strange shapes like area with light blue color in the figure 1 because the former owner has a strange sense.

The shape of an original window is a polygon with n + 1 vertices, and at least one of its edges is parallel to the ground. You decide to convert a strange window to a rectangular window by making new walls to extra space. This rectangle should have an edge which is parallel to the ground. For example, you can convert the strange window in figure 1 to a rectangular window by making new walls to areas with brown color in figure 2. This is the same situation in the sample input.

Your job is to write a program to calculate the area of a largest rectangular window.

输入格式

Input consists of multiple test cases. The first line of each test case contains a single positive integer n ( n <= 1,024). The following n lines contain two positive integers xi ( 0 < xi < x i+1 < 1,000,000)、 y i ( 0 < yi< 1,000,000 ) indicating a coordinate of a vertex, separated by a single space character. You can assume that the most left vertex is always located on the origin of the coordinates. You can also assume that ynis always 0. Input is terminated by a case of n = 0, and it should not be processed.

输出格式

For each test case, you should output the size of a maximum rectangular window to each line. You should output at least 3 digits and at most 5 digits after the decimal point. Each area may not have an error greater than 0.001.

样例

Input
4
2 2
3 1
4 2
5 0
0
Output
3.500

0 人解决,0 人已尝试。

0 份提交通过,共有 0 份提交。

9.9 EMB 奖励。

创建: 12 年,10 月前.

修改: 4 年前.

最后提交: N/A.

来源: International Maximum-Cup 2008

题目标签