0

I am not clear about problem 15 (One rectangle) of ACM MIPT (http://acm.mipt.ru/judge/problems.pl?problem=015), specifically sample test case 2. Shouldn't the maximum rectangle for that case have area 2500 (rectangle being the one with vertices at (25, 25), (0, 50), (50, 100), (75, 75))? Here is the problem statement:

In the square 0 ≤ x ≤ 100, 0 ≤ y ≤ 100 there are N points with integer coordinates. You should find out rectangle which has no any of given point (meaning none of the given points??) inside and has maximum possible area.

Remark: Points are permitted to be on the border of the rectangle.

Input: First line has the number N, 1 ≤ N ≤ 100, next N lines has coordinates of N points.

Output: Your program should output one number — maximum area.

Input#1
1
50 50

Output#1
5000

Input#2
3
25 25
50 50
75 75

Output#2
3750

4

1 回答 1

1

不，给出的答案是正确的。

如果考虑具有以下端点的矩形，则 3750 为面积：

(0, 50), (75, 50), (75, 100), (0,100)。

注意：它接触点：(50, 50) 和 (75, 75) 但里面没有三个点中的任何一个。

希望有帮助！

于 2012-09-25T11:37:09.113 回答