3336 : 직각다각형

다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다.

다각형의 가 변이 x축과 y축에 평행한 다각형을 직각다각형이라고 부른다.

단순다각형이면서 직각다각형을 단순직각다각형이라 부른다.

아래 두 그림은 단순직각다각형의 예를 보여준다.

단순직각다각형이 주어질 때,

수평선 H가 다각형의 수직선분과 몇 번 교차하는지 또는 수직선 V가 다각형의 수평선분과 몇 번 교차하는지 알고자 한다.

첫 번째 그림에서 수평선 H가 4개의 수직선분과 교차하고 수직선 V는 2개의 수평선분과 교차한다.

두 번째 그림은 첫 번째 그림에서 수평선 H의 위치를 조금 위로 옮긴 것으로 8개의 수직선분과 교차하게 된다.

이 때, 단순직각다각형과 가장 많이 교차하는 수평선 H와 수직선 V의 위치를 찾아 그때의 교차 횟수를 구하고자 한다.

단, 수평선 H는 다각형의 어떤 수평선분과도 겹쳐 놓여서는 안 되고,

유사하게 수직선 V는 다각형의 어떤 수직선분과도 겹쳐 놓여서는 안 된다.

수평선 H의 위치를 잘 정해서 주어진 단순직각다각형의 수직선분과 가장 많이 교차하는 지점을 찾을 때,

그 때의 교차 횟수를 h라 하고, 유사하게 수직선 V와 주어진 단순직각다각형의 수평선분과

가장 많이 교차하는 횟수를 v라 할 때, max(h,v)를 출력하는 프로그램을 작성하시오.

입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4≤n≤100,000)이 주어지고,

이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (x1,y1)(1≤i≤n)가 차례대로 주어진다.

주어지는 꼭지점들의 순서는 시계방향이다.

다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000≤x1,y1≤500,000 이다.

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

채점기준

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

모든 테스트 케이스를 맞았을 시 100점을 받는다. 각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다.

그룹1, 총 38점 상당의 테스트 케이스로 구성되어 있다. 각각 4≤n≤1,000을 만족한다.

그룹2, 총 62점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.

KOI 1차 2019 중2- 직각다각형 > 문제은행 : 정보올림피아드&알고리즘