회전 기둥

OBS!!! 이 문제에서 다루는 기둥은 그룹 나누기 문제의 기둥과 같은 종류가 아니다

당신의 하늘을 나는 양탄자가 말썽을 부리기 시작했다! 양탄자가 비어 있는 동안에는 모든 것이 순조로워서 평면 어디든 문제없이 날아갈 수 있다. 하지만 마법의 기름 램프 같은 물건을 싣는 순간부터는 스스로 방향을 바꿀 수 없고, 이른바 회전 기둥에서 방향을 바꿔야 한다. 회전 기둥은 한 번에 반시계 방향으로 90도만 회전할 수 있으므로 양탄자도 방향을 바꿀 때마다 정확히 반시계 방향으로 90도만 돌 수 있다. 게다가 무언가를 싣는 순간 너무 빨리 과열되어 불타는 흔적을 남긴다. 따라서 같은 기둥에서 여러 번 방향을 바꿀 수도 없다. 그러면 너무 오래 걸려 양탄자가 불타 버릴 것이다. 또한 양탄자는 자신의 경로를 가로지르거나 이미 방문한 기둥을 다시 방문할 수도 없다.

물론 양탄자의 상태가 그 어느 때보다 나쁜 바로 지금, 당신은 어느 때보다 양탄자가 필요하다. Rafaj가 술탄의 모든 마법 기름 램프를 도시의 회전 기둥들에 흩어 놓았기 때문이다. 누군가 실수로 정령들을 풀어 주어 재앙이 현실이 되기 전에 가능한 한 많은 기름 램프를 모아야 한다.

평면에는 정수 좌표를 가진 $n$개의 회전 기둥이 있으며, 이제 각 기둥에는 마법 기름 램프가 하나씩 있다. 다음과 같은 방식으로 이동하여 하늘을 나는 양탄자로 가능한 한 많은 기둥을 방문하려고 한다.

• 양탄자가 비어 있을 때는 자유롭게 날 수 있으므로 임의의 기둥에서 시작할 수 있다

• 위/아래/왼쪽/오른쪽으로만 이동할 수 있다

• 기둥에서만 방향을 바꿀 수 있으며, 반시계 방향으로 90도만 돌 수 있다. 즉, 시계 방향으로 돌거나 반대 방향으로 되돌아갈 수는 없지만 직진할 수는 있다

• 경로가 자기 자신과 교차하거나 같은 기둥을 여러 번 방문해서는 안 된다. 그러면 양탄자가 불타 버린다

몇 개의 기둥을 방문할 수 있는가?

점수

해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ | $19$ | $n \leq 25, x_{i}, y_{i} \leq 5$

$2$ | $16$ | $n \leq 80, x_{i}, y_{i} \leq 80$

$3$ | $20$ | $n \leq 80$

$4$ | $45$ | 추가 제한 없음

첫 번째 줄에는 정수 $n$ ($1 \leq n \leq 1000$)이 주어진다. 이후 $n$개의 줄이 이어진다. $i$번째 줄에는 $i$번째 기둥의 좌표를 나타내는 두 양의 정수 $x_{i}, y_{i}$ ($1 \leq x_{i}, y_{i} \leq 10^9$)이 주어진다. 두 기둥이 같은 위치에 놓이는 경우는 없다.

방문할 수 있는 기둥 수의 최댓값을 나타내는 정수 하나를 한 줄에 출력한다.