b_창고 다각형_2304

문제

w : 1 , h : n
지붕 특

• 모두연결되어야함
• 수평부분 : 어떤 기둥의 윗면과 닿아야함
• 수직부분 : 어떤 기둥의 옆면과 닿아야함
• 가장자리는 땅에 닿아야
• 오목한부분 없어야

답

틀렸던 생각

아래의 케이스가 있을 것 같다고 생각하고 고점 기준으로 좌-우로 접근하면 된다고 생각.
기울기로 본다면

• • 고점 -
• 고점 -
• • 고점
    어느정도 맞으나 오른쪽은 계속 이후 조건이 내가선택한조건보다 작은지 확인해야하고 구현적으로 불편함

맞은답

위에서 접근한다고 생각함
높이 순으로 정렬해 최고점은 우선 빼서 선택해놓고 좌 우 붙이는 느낌

1. heapq를 이용하여서 넣는데로 높이순으로 정렬
2. 가장 높은 값을 기준으로 둠
3. 왼쪽과 오른쪽 x값을 높은 값기준으로 초기화
4. 힙큐 하나씩 빼면서 현재 진행한 가장 왼쪽의 x보다 더 왼쪽이거나, 가장 오른쪽의 x보다 더 오른쪽이면 넓이 추가

import sys
import heapq

N=int(sys.stdin.readline().strip())
startx , endx = 1001, -1

heap = []
for _ in range(N):
    x , y= map(int,sys.stdin.readline().strip().split())
    if startx > x: startx = x
    if endx < x : endx = x
    heapq.heappush(heap,(-y,x))

before = heapq.heappop(heap)
area = - before[0]
leftx , rightx = before[1],before[1]
while heap:
    now = heapq.heappop(heap)
    if leftx > now[1]:
        area += -now[0] * (leftx - now[1])
        leftx = now[1]
    elif rightx < now[1]:
        area += -now[0] * (now[1]-rightx)
        rightx = now[1]
    else:
        continue
    # print(before,now,area)

print(area)