Informatica Online Judge

  피벗의 평면 분할 [1188 / 04A4]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 23   Total Tried : 35


The Champion of this Problem (C++) : gs17018 - ms / 897byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

좌표평면 위에 n개의 점이 있다. 이 점들은 모두 격자점에 위치하고 있다. (격자점이란 x, y모두 정수좌표를 가지는 점을 의미한다.)

그리고 어떤 점의 위치가 (X, Y)라고 하면, x의 값이 X인 점은 존재하지 않으며, y축의 값이 Y인 점은 존재하지 않는다.

이러한 점들 중 하나를 피벗으로 설정하면 아래 그림과 같이 피벗을 원점으로 하는 A, B, C, D의 네 영역으로 나뉜다.



각 영역은 정해진 점수가 있다. A영역은 a점, B영역은 b점, C영역은 c점, D영역은 d점이라고 할 때, 피벗의 점수는 다음과 같이 계산할 수 있다.

임의의 피벗의 점수 = 각 영역의 점수*해당 영역의 점의 수
따라서 위 그림의 경우에 획득하는 점수는 2*a + 2*b + c + d 점이 된다.

좌표평면에 n개의 점의 좌표가 주어질 때, 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 점의 수 n이 입력된다.
두 번째 줄에 각 영역의 점수 a, b, c, d가 공백으로 구분되어 입력된다.
다음 줄부터 n줄에 걸쳐서 각 점의 x, y좌표가 공백으로 구분되어 입력된다.
(각 좌표의 절댓값은 100,000,000을 넘지 않는다.)

[Sub-task Info]
#1 : n <= 1,000 (30%)
#2 : n <= 100,000 (70%)

Output

얻을 수 있는 최대 점수를 출력한다.
(답은 항상 32bit 정수값을 초과하지 않는다.)

IO Example

입력
4
2 -1 3 1
0 0
-1 -2
-2 -1
2 1

출력
9

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]