COCI 2014/2015 contest1 2- 모기 덫(KLOPKA) > 문제은행 : 정보올림피아드&알고리즘




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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP