문제
2차원 평면상에서 직각다각형은 그 변을 구성하는 선분이 수직이거나 수평인 다각형이다.
일반 직각다각형이란 그 변을 이루는 선분이 서로 교차할 수 있는 직각다각형이고,
단순 직각다각형이란 그 변을 이루는 선분이 서로 교차하지 않는 다각형이다.
이 문제에서 다루고자하는 다각형은 일반 직각다각형이면서 다음 조건을 만족하는 직각다각형이다.
① 다각형의 꼭지점은 서로 같은 지점에 위치할 수 없다. ② 다각형의 각 꼭지점에서는 다각형의 변을 이루는 하나의 수직선분과 하나의 수평선분이 그 선분의 끝점에서 만난다. ③ 다각형의 변이 교차하는 경우는 반드시 수평선분과 수직선분 사이에 교차한다.
즉, 수평선분끼리 교차하거나, 수직선분끼리 교차하는 경우는 없다.
![](https://u.jungol.co.kr/problem/1572/adadbbef-44c9-4f54-97d3-759865d2dcdf.png)
이렇게 구성된 일반 직각다각형은 평면을 여러 개의 단순 직각다각형으로 분할하게 된다.
예를 들면, 아래 그림은 14개의 선분으로 구성된 일반 직각다각형이다.
이 직각다각형은 다각형의 외부는 제외하고 평면을 6개의 단순 직각다각형 A, B, C, D, E, F 로 분할하고 있으며,
이들 단순 직각다각형 중에서 가장 면적이 넓은 다각형은 F 이다.
일반 직각다각형이 주어졌을 때, 이 직각다각형에 의하여 분할되는 단순 직각다각형 중에서
그 면적이 가장 큰 단순 직각다각형의 면적을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 일반 직각다각형의 꼭지점의 개수를 나타내는 정수 N ( 4≤N≤1,000) 이 나온다.
다음 N 개의 줄에는 각각 하나의 꼭지점에 대한 좌표를 나타내는 두 개의 정수 x와 y( 0≤x,y≤10, 000)가 입력된다.
첫 번째 정수 x는 그 꼭지점의 X-좌표를 나타내며, 두 번째 정수 y는 그 꼭지점의 Y-좌표를 나타낸다.
연속되는 두 개의 꼭지점을 선분으로 연결하고, 마지막 꼭지점과 첫 번째 꼭지점을 연결하면 입력되는 일반 직각다각형이 구성된다.
출력
예제1
8
1 1
5 1
5 6
3 6
3 2
8 2
8 4
1 4
8
예제2
14
1 7
2 7
2 6
7 6
7 2
3 2
3 7
6 7
6 3
11 3
11 1
5 1
5 4
1 4
10