문제
다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다.
다각형의 가 변이 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개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi,yi)(1≤i≤n)가 차례대로 주어진다.
주어지는 꼭지점들의 순서는 시계방향이다.
다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000≤xi,yi≤500,000 이다.
출력
표준 출력으로 각각 수평선 H, 수직선 V와 단순직각다각형의 최다 교차 횟수를 h,v라 할 때, max(h,v)를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 38점 |
|
| #2 | 62점 |
|
예제1
4
-1-1
-11
11
1-1
2
예제2
12
00
03
13
11
21
23
53
50
40
42
32
30
6