인프런 커뮤니티 질문&답변

import sys

sys.stdin =  open('BackJoon/3강_누적합/5_17611.txt','r')

input =  sys.stdin.readline
n = int(input())

vertex = [list(map(int, input().split())) for _ in range(n)]

######## (x_min, y_min) -> (0, 0)으로 이동
x_min, x_max = 500000, -500000
y_min, y_max = 500000, -500000
for x,y in vertex:
    x_min = min(x, x_min)
    x_max = max(x, x_max)
    y_min = min(y, y_min)
    y_max = max(y, y_max)

x_diff = 0 - x_min
y_diff = 0 - y_min
for i in range(n):
    vertex[i][0] = vertex[i][0] + x_diff
    vertex[i][1] = vertex[i][1] + y_diff

##### 수평선 조사 (강의에서와 같이 왼쪽으로 돌려서 봄)
vertex_x_incre = sorted(vertex, key = lambda x: (x[0], x[1])) # 

y_range = y_max-y_min+1
x_range = x_max-x_min+1

x_sum_list = [0] * (y_range+1) # x축 방향으로 [1, 0, 0, ..., -1] 더함

for i in range(0,n,2): # 선분은 2개의 꼭지점으로 이루어짐
    v1 = vertex_x_incre[i]
    v2 = vertex_x_incre[i+1]

    if v1[0] != v2[0]: # 디버깅
        print('x point does not match!!')#만약 선분이 직선이 아니라면(혹은 sort가 잘못됨)
        break
    if v1[1] >= v2[1]:
        print('y point does not align!!')#sort가 잘못됨
        print('v1:', v1)
        print('v2:', v2)
        break

    x_sum_list[v1[1]] += 1
    x_sum_list[v2[1]] -= 1

x_sum_list = x_sum_list[:-1] #범위밖의 맨 마지막 -1 자리 버림

prefix = [0]*(y_range+1)
for i in range(y_range):
    prefix[i+1] = prefix[i] + x_sum_list[i]
prefix = prefix[1:]
h = max(prefix)


##### y축 방향으로 조사 (수직선 조사)
vertex_y_incre = sorted(vertex, key = lambda x: (-x[1], x[0]))

y_sum_list = [0] * (x_range+1) # y축 방향으로 [1, 0, 0, ..., -1] 더함

for i in range(0,n,2):
    v1 = vertex_y_incre[i]
    v2 = vertex_y_incre[i+1]
    if v1[1] != v2[1]:
        print('y point does not match!!')
        break
    if v1[0] >= v2[0]:
        print('x point does not align!!')
        print('v1:', v1)
        print('v2:', v2)
        break
    y_sum_list[v1[0]] += 1
    y_sum_list[v2[0]] -= 1

y_sum_list = y_sum_list[:-1]

prefix = [0]*(x_range+1)
for i in range(x_range):
    prefix[i+1] = prefix[i] + y_sum_list[i]
prefix = prefix[1:]

v= max(prefix)
print(max(h,v))