다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다. 다각형의 각 변이 \(x\)축과 \(y\)축에 평행한 다각형을 직각다각형이라 부른다. 단순다각형이면서 직각다각형을 단순직각다각형이라 부른다. 아래 두 그림은 단순직각다각형의 예를 보여준다.

단순직각다각형이 주어질 때, 수평선 \(H\)가 다각형의 수직선분과 몇 번 교차하는지 또는 수직선 \(V\)가 다각형의 수평선분과 몇 번 교차하는지 알고자 한다. 첫 번째 그림에서 수평선 \(H\)는 \(4\)개의 수직선분과 교차하고 수직선 \(V\)는 \(2\)개의 수평선분과 교차한다. 두 번째 그림은 첫 번째 그림에서 수평선 \(H\)의 위치를 조금 위로 옮긴 것으로 \(8\)개의 수직선분과 교차하게 된다.

이때, 단순직각다각형과 가장 많이 교차하는 수평선 \(H\)와 수직선 \(V\)의 위치를 찾아 그때의 교차 횟수를 구하고자 한다. 단, 수평선 \(H\)는 다각형의 어떤 수평선분과도 겹쳐 놓여서는 안 되고, 유사하게 수직선 \(V\)는 다각형의 어떤 수직선분과도 겹쳐 놓여서는 안 된다.

수평선 \(H\)의 위치를 잘 정해서 주어진 단순직각다각형의 수직선분과 가장 많이 교차하는 지점을 찾을 때, 그때의 교차 횟수를 \(h\)라 하고, 유사하게 수직선 \(V\)의 위치를 정해 주어진 단순직각다각형의 수평선분과 가장 많이 교차하는 횟수를 \(v\)라 할 때, \(\max(h, v)\)를 출력하는 프로그램을 작성하시오.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

입력의 첫 줄에는 단순직각다각형의 꼭짓점의 개수를 나타내는 정수 \(n\ (4 \le n \le 100{,}000)\)이 주어지고, 이어지는 \(n\)개 줄에는 단순직각다각형 꼭짓점의 좌표 \((x_i, y_i)\ (1 \le i \le n)\)가 차례대로 주어진다. 주어지는 꼭짓점들의 순서는 시계방향이다. 다각형의 꼭짓점을 나타내는 각 좌표값은 정수이며, \(-500{,}000 \le x_i, y_i \le 500{,}000\)이다.

표준 출력으로 각 수평선 \(H\), 수직선 \(V\)와 단순직각다각형의 최대 교차 횟수를 각각 \(h\), \(v\)라 할 때, \(\max(h, v)\)를 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 중등부 2번