2867 : 모기 덫(KLOPKA)
- 제한시간
- 1000 ms
- 메모리제한
- 32 MB
- 해결횟수
- 72 회
- 시도횟수
- 154 회
문제
여름이 다가오면서 바이트시는 모기로 몸살을 앓고 있다. 이 문제를 해결하기 위하여 제안된 여러 가지 방법 중에 한 가지 방법이 있는데 모기 발생지를 찾아 전체를 정사각형 모기 덫으로 씌워 모기를 잡자는 것이다.
모기 발생지가 주어질 때 전체 모기 발생지를 덮는 축에 평행한 정사각형 모기 덫의 최소 면적을 구하는 프로그램을 작성하여 이 방법의 효율성을 검증해 보자.
입력형식
첫 행에 모기 발생지역의개수 N( 1 ≤ N ≤ 20)이 주어진다.
다음 N개의 행에 모기 발생지역의 2차원 좌표 Xi, Yi (1 ≤ Xi, Yi ≤ 100)가 주어진다.
출력형식
주어진 좌표의 모기를 전부 잡을 수 있는 변이 축에 평행한 정사각형 모기 덫의 최소 면적을 구하여 출력한다.
<입력 예 1에 대한 설명>
가능한 정사각형은 (3, 3)에서 (7, 7)까지의 사각형이다.
입력 예3 3 4 5 7 4 3 |
출력 예16 |
입력 예4 1 5 5 1 10 5 5 10 |
출력 예81 |