정올 직각다각형

문제

예제

 

import sys
input = sys.stdin.readline

N = int(input())

arr = []
for _ in range(N):
    x,y= map(int,input().split())
    arr.append((x,y))

MID = 500_000
TOTAL = MID * 2 + 1
H,V = 0, 1

def solve(hv):
    line = [0] * TOTAL
    for cur in range(hv,N,2):
        nxt = (cur+1) if cur + 1 != N else 0
        j = 0
        if arr[cur][0] == arr[nxt][0]:
            j=1
        min_p,max_p = sorted([arr[cur][j], arr[nxt][j]])
        line[min_p + MID] += 1
        line[max_p + MID] -= 1
    
    ans,tot = 0,0
    for i in line:
        tot += i
        ans = max(ans,tot)
    return ans

ans = max(solve(H), solve(V))
print(ans)

이 코드는 주어진 NN개의 좌표를 순서대로 연결해 다각형을 만들고, 이 다각형을 구성하는 선분들 중 수평선과 수직선 각각에서 가장 많이 겹치는 지점을 찾아내는 프로그램이다. 먼저 좌표를 입력받아 리스트에 저장하고, 각 선분의 방향에 따라 수평(H) 또는 수직(V)으로 분류한 뒤, 각 방향에 대해 누적 합 방식(Prefix Sum)을 사용하여 겹치는 선분의 개수를 효율적으로 계산한다. 이를 위해 좌표 범위를 보정하기 위해 기준값인 500,000을 더해 음수 인덱스를 피하고, 시작점과 끝점에서 각각 1씩 더하고 빼는 방식으로 선분의 존재를 표시한 다음, 전체 배열을 순회하며 누적합을 구해 동시에 겹치는 선분의 최대 개수를 찾는다. 이렇게 수평선과 수직선에 대해 각각 계산한 뒤, 두 값 중 더 큰 값을 정답으로 출력함으로써 가장 많은 선분이 겹치는 지점이 몇 개인지를 구하도록 되어 있다.