코로나 바이러스 서브태스크 5초 512MB
문제
KOI국은 xy 평면으로 표현될 수 있다. KOI 국에는 N개의 집이 있으며 i번째 집(1 ≤ i ≤ N) 의 좌표는 (Xi, Yi)이다.
모든 집의 좌표가 서로 다름이 보장된다. 또한, i번째 집에는 i번째 시민이 산다.
KOI국에 명절이 찾아와 시간 0에, 모든 시민들은 동서남북 중 방향을 하나 골라 그 방향으로 시간당 1의 좌표의 속도로 이동하기 시작한다.
만약 i번째 사람이 동쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi + t, Yi)가 된다.
만약 i번째 사람이 서쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi - t, Yi)가 된다.
만약 i번째 사람이 남쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi, Yi - t)가 된다.
만약 i번째 사람이 북쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi, Yi + t)가 된다.
하지만, 시간 0에 시민 1은 코로나에 걸려 있다. 만약 어떤 시간에 시민 a, b (1 ≤ a ≤ N), (1 ≤ b ≤ N)가 동일한 위치에 있으며
a는 코로나에 걸려 있고 b는 코로나에 걸려 있지 않는다면 b 또한 코로나에 걸리게 된다.
안타깝게도 아직 백신이 개발되지 않아 코로나 바이러스는 치유되지 않는다.
각 사람들이 이동할 방향을 아직 정하지 않은 상태이다. 새로운 정부에서 보건복지부 장관으로 임명된 당신은
최악의 상황에서 10^100의 시간이 흘렀을 때 최대 몇명의 사람들이 감염될 수 있는지 구해야 한다.
1 ≤ N ≤ 100 000.
0 ≤ Xi ≤ 500 000 000 (1 ≤ i ≤ N).
0 ≤ Yi ≤ 500 000 000 (1 ≤ i ≤ N).
(Xi, Yi) ≠ (Xj, Yj) (1 ≤ i < j ≤ N).
Subtask 1 (5점) : N ≤ 7, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)
Subtask 2 (8점) : N ≤ 15, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)
Subtask 3 (6점) : N ≤ 100, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N), X1 = 0, Y1 = 0
Subtask 4 (6점) : N ≤ 100, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)
Subtask 5 (12점) : N ≤ 3 000
Subtask 6 (32점) : Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)
Subtask 7 (31점) : 추가 제한 조건 없음
입력
N
X1 Y1
X2 Y2
...
XN YN
출력
첫 줄에 10^100의 시간 후 감염자의 수의 최댓값을 출력하시오.
예제 #1
2
0 0
4 3
1
예제 #2
3
1 2
2 1
4 3
3
예제 #3
2
20 20
20 21
2
예제 #4
15
5 6
2 9
12 0
4 11
3 12
6 5
0 8
9 10
11 13
8 7
13 2
1 1
7 14
10 4
14 3
9
예제 #5
30
275810186 246609547
122805872 99671769
243507947 220373844
281305347 252104708
237805644 214671541
172469077 149334974
222589229 229887956
160653451 208404690
241378966 211098219
144302355 224755786
186392385 163258282
199129390 169928751
294937491 265736852
196096122 172962019
314342944 285142305
202720470 166337671
157037485 133903382
263858979 240724876
210720220 181519581
296402036 267201397
186021287 183036854
195081930 173976211
328293029 299092390
261195361 238061258
323595085 294394446
299933764 270733125
240976723 128081418
188501753 165367650
277832422 248631783
119896220 96762117
11
로그인해야 코드를 작성할 수 있어요.