2620번 - 직각다각형의 면적 구하기

2차원 평면상에서 직각다각형은 그 변을 구성하는 선분이 수직이거나 수평인 다각형이다. 일반 직각다각형이란 그 변을 이루는 선분이 서로 교차할 수 있는 직각다각형이고, 단순 직각다각형이란 그 변을 이루는 선분이 서로 교차하지 않는 다각형이다. 이 문제에서 다루고자하는 다각형은 일반 직각다각형이면서 다음 조건을 만족하는 직각다각형이다.

1. 다각형의 꼭짓점은 서로 같은 지점에 위치할 수 없다.
2. 다각형의 각 꼭짓점에서는 다각형의 변을 이루는 하나의 수직선분과 하나의 수평선분이 그 선분의 끝점에서 만난다.
3. 다각형의 변이 교차하는 경우는 반드시 수평선분과 수직선분 사이에 교차한다. 즉, 수평선분끼리 교차하거나, 수직선분끼리 교차하는 경우는 없다.

이렇게 구성된 일반 직각다각형은 평면을 여러 개의 단순 직각다각형으로 분할하게 된다. 예를 들면, 아래 그림은 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-좌표를 나타낸다. 연속되는 두 개의 꼭짓점을 선분으로 연결하고, 마지막 꼭짓점과 첫 번째 꼭짓점을 연결하면 입력되는 일반 직각다각형이 구성된다.

첫 번째 줄에 입력되는 일반 직각다각형에 의하여 분할되는 가장 면적이 큰 단순 직각다각형의 면적을 나타내는 정수를 출력한다.

실제 기출문제의 문제 제목은 "직각다각형의 면적" 이다.