Python 28제] 2019년 한국정보올림피아드 1차대회 중등부 유형3. 2번-직각다각형

문제]

다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다. 다각형의 각 변이 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)(4≤i≤n)가 차례대로 주어진다. 주어지는 꼭지점들의 순서는 시계방향이다. 다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000 ≤ xi, yi ≤ 500,000이다.

 

출력형식

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

 

입력/출력 예시]

입력1

4

-1 -1

-1 1

1 1

1 -1

 

출력1

2

 

입력2

12

0 0

0 3

1 3

1 1

2 1

 

출력2

6

 

 

 

출처 : 한국정보올림피아드(2019년도 한국정보올림피아드 1차 대회 중등부 2교시 문제)

 

 

참고풀이]

import sys #exit()

#꼭지점의 범위 -500,000≤xi,yi≤500,000의
#갭은 1,000,000이므로 최대값을 1,000,002로 잡음.
MAXL = 1000002
ly = [0]*MAXL
lx = [0]*MAXL
px = []
py = []

#단순직각다각형의 꼭지점의 개수를 입력한다.
N = int(input())
if 4<=N<=100000:
    for i in range(N):
        x, y = map(int, input().split())
        if -500000<=x<=500000 and-500000<=y<=500000:
            x = x + MAXL // 2
            y = y + MAXL // 2
            px.append(x)
            py.append(y)
        else:
            sys.exit()
        
    #x선 또는 y선을 기준으로 하는 통과선의 개수를 구한다    
    for i in range(N):
        j = (i + 1) % N
        if px[i] == px[j]:
            y1, y2 = py[i], py[j]
            if y1 < y2:
                ly[y1] += 1
                ly[y2] -= 1
            else:
                ly[y2] += 1
                ly[y1] -= 1
        else:
            x1, x2 = px[i], px[j]
            if x1 < x2:
                lx[x1] += 1
                lx[x2] -= 1
            else:
                lx[x2] += 1
                lx[x1] -= 1

#같은 수평 또는 수직선에 해당하는 선수들의 합을 구한다.                
for i in range(MAXL//2-N,MAXL//2+N*2):
    lx[i] += lx[i-1]
    ly[i] += ly[i-1]

#수평 또는 수직선들의 합들 중 최대값을 출력한다.    
print(max(max(lx),max(ly)))

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도

https://youtu.be/muB4_LNZ2Rk