둘레길

시간 제한2초메모리 제한512 MB

요약

서로 다른 정수 좌표 점이 최대 500개 주어질 때, 축에 평행한 직사각형의 둘레 위에 놓을 수 있는 점의 최대 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 완전 탐색, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

연우는 한국 어딘가에 있는 조그마한 시의 시장이다. 연우의 시에는 총 $N$ ( $1 \le N \le 500$ )개의 관광 명소가 있다. $i$ 번째 관광 명소는 $(x_i, y_i)$ 지점에 위치해 있다( $-10^9 \le x_i, y_i \le 10^9$ , $x_i, y_i$ 는 정수).

연우는 관광 사업을 준비 중이다. 연우는 시에 사각형 모양의 둘레길을 만들어서 사람들이 이 둘레길을 따라 움직이며 관광 명소들을 볼 수 있게 하고 싶다.

당연히 둘레길을 따라 최대한 많은 관광 명소를 둘러볼 수 있는 게 좋을 것이다. 즉, 사각형을 하나 그려서 이 사각형의 둘레(변) 위에 존재하는 관광 명소의 개수가 최대가 되게 하고 싶다.

이때 미관상의 이유로 둘레길은 축에 평행한 직사각형의 형태여야 한다.

연우를 도와 각 관광 명소의 좌표가 주어졌을 때 둘레길을 어떻게 설치해야 최대한 많은 관광 명소를 지날 수 있는지 계산하는 프로그램을 작성해 보자.

입력

첫째 줄에 연우의 시에 존재하는 관광 명소의 개수 $N$ ( $1 \le N \le 500$ )이 주어진다.

둘째 줄부터 $N$ 줄에 걸쳐 각 관광 명소의 좌표 $x_i$ 와 $y_i$ 가 공백으로 구분되어 주어진다( $-10^9 \le x_i, y_i \le 10^9$ ). 모든 관광 명소의 위치는 서로 다르다.

출력

첫째 줄에 둘레길 위에 포함할 수 있는 관광 명소의 최대 개수를 출력한다.

예제3

예제 1
입력
```
5
2 1
1 4
3 5
4 4
4 2
```
예상 출력
```
5
```
예제 2
입력
```
4
1 1
1 2
1 3
1 4
```
예상 출력
```
4
```
예제 3
입력
```
7
1 2
1 4
1 6
4 2
2 3
3 5
4 4
```
예상 출력
```
5
```