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


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

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

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

채점기준
제출된 프로그램은 여러 개의 테스트 케이스로 평가되며, 맞은 테스트 케이스에 대해서 해당 테스트 케이스에 배정된 점수를 받는다. 모든 테스트 케이스를 맞았을 시 100점을 받는다.

각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다:
1. (38점) \(4 \le n \le 1,000\)
2. (62점) 제약 조건 없음

입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 \(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)\)를 출력한다.

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2019KOI1차