COCI 2017/2018 contest6 4- 점 덮기 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4826 : 점 덮기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
9 회   
시도횟수
69 회   

문제

2차원 평면에 점들이 주어집니다. 주어진 모든 점들은 하나 이상의 직사각형으로 덮어져야 합니다. 또한 같은 조건을 만족해야 합니다.

 

- 직사각형의 모든 변들은 좌표축과 평행합니다.

- 직사각형의 중앙은 원점(0,0)입니다. 

- 점을 덮는다는 것은 그 점이 직사각형 안에 있거나 경계선 위에 있다는 것입니다.

 

물론, 큰 직사각형 하나로도 모든 점들을 덮을 수는 있지만 면적이 넓습니다.

모든 점들을 하나 또는 여러 직사각형으로 덮을 때 직사각형 면적 합의 최소를 구하는 프로그램을 작성하세요. 

 


입력형식

첫 번째 줄에 점들의 수 N이 주어집니다. (1 ≤ N ≤ 5000)

그 다음 각 줄마다 N개의 점들의 좌표 X, Y가 주어집니다. (-50 000 000 ≤ X, Y ≤ 50 000 000 , XY ≠ 0)


출력형식

모든 점을 덮을 수 있는 직사각형 면적들의 합의 최소를 출력합니다.


입력 예

복사하기

2
1 1
-1 -1

출력 예

복사하기

4

입력 예

복사하기

3
-7 19
9 -30
25 10

출력 예

복사하기

2080

입력 예

복사하기

6
1 20
3 17
5 15
8 12
9 11
10 10

출력 예

복사하기

760


경기도 안양시 동안구 평촌대로 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