[Python] 백준 14751 - Leftmost Segment

https://www.acmicpc.net/problem/14751

문제

There are two distinct horizontal lines hupper and hlower in the xy-coordinate plane and n line segments connecting them. One endpoint of each segment lies on hupper and the other on hlower. All endpoints of the segments are distinct. All segments are numbered from 1 to n. Consider a horizontal line hi located between hupper and hlower, which will be given by a query. The line hi crosses all segments definitely. We want to know which segment intersects at the leftmost with hi. You can observe that the leftmost intersection point between the segments and a query line may lie on one or more segments since two or more segments may intersect at a single point. In that case, the leftmost segment is defined as the segment which has the leftmost endpoint on hupper.

For example, 5 segments and 3 query lines are given in the plane as shown in the figure below. The leftmost segment that intersects with a query line of y = 2.0 is 2 and the leftmost segment that intersects with a query line of y = 4.0 is 3. The query line of y = 6.25 crosses the intersection point between the segments 3 and 4, hence the leftmost segment is 4 by definition.

Given n segments connecting two horizontal lines and m queries, you are to write a program to find the leftmost segment that intersects with each query line.

Note that two or more segments may intersect at a single point. You should be also careful of round-off errors caused by the computer representation of real numbers.

입력

Your program is to read from standard input. The input starts with a line containing two integers, maxY and minY (-1,000 ≤ minY < maxY ≤ 1,000), where maxY and minY represent the y-coordinates of the upper horizontal line and the lower horizontal line, respectively. The next line contains an integer n (1 ≤ n ≤ 100,000) which is the number of segments connecting two horizontal lines. All segments are numbered from 1 to n in order given as the input. In the following n lines, each line contains two integers upperX and lowX (-500,000 ≤ upperX, lowX ≤ 500,000) which represent the x-coordinates of the upper endpoint and the lower endpoint of a line segment, respectively. All endpoints are distinct. The next line contains an integer m (1 ≤ m ≤ 100,000) which is the number of queries. In the following m lines, each line contains a y-coordinate given for the query horizontal line, which is a real number between minY and maxY exclusive and the number of digits after the decimal point is 1 or more and 3 or less.

출력

 

Your program is to write to standard output. Print exactly one line for each query in order given as the input. The line should contain the leftmost segment number which intersects with the query horizontal line.

 

문제요약

y = a, y = b의 두 가로선이 있고, 이 두 가로선을 잇는 선분들이 여러 개 주어집니다. y = q의 쿼리가 주어질 때 y = q와 만나는 선분들 중 가장 왼쪽에 있는 선분의 번호를 출력하세요.

---

 

풀이

지난번 글에서 다루었던 Convex Hull Trick 의 핵심 아이디어만 응용한 문제이다.

정확히 말하자면 Convex Hull Trick의 기하학적인 구현 부분만 따다가 문제로 만든 것으로 볼 수 있다.

 

주어진 그림을 한 번 뒤집고 90도 회전하면 우리가 평소에 보는 CHT의 모습이 된다.

 

이미지를 뒤집고 돌렸다. 이제 우리에게 친숙한 모양이다!

그리고 구현의 편의상 문제에서 주어진 모든 X를 Y로 바꾸고 Y를 X로 바꾸겠다.

 

보통 다른 CHT 문제들의 경우에는 선분의 기울기가 오름차순/내림차순으로 정렬되어서 주어지고, 더 친절한 경우에는 쿼리마저 정렬되어 주어진다.

 

근데 이 문제는 둘 다 아니다.

 

따라서 쿼리를 처리하기 위해서는 이분 탐색을 써야 할 것이고, 선분같은 경우는 먼저 임시 리스트에 받아놓고, 기울기와 y절편을 기준으로 정렬을 해 준 다음 함수를 관리해주어야 할 것이다.

 

일단 선분(일차함수) 입력을 받아보자.

 

기울기는(앞으로 나오는 모든 변수 이름의 X, Y는 뒤바껴있다)

(upperY - lowY) / (maxX - minX)

 

절편은

(lowY * maxX - upperY * minX) / (maxX - minX)

 

그리고 함수를 [기울기, 절편, 최소구간 시작점, 선분 번호] 의 형식으로 관리한다.

 

그럼 여기까지 임시로 선분들을 입력받아놓는 코드는

 

tmpf = []
for i in range(n):
    upperY, lowY = map(int, input().split())
    dydx = (upperY - lowY) / (maxX - minX)
    jeol = (lowY * maxX - upperY * minX) / (maxX - minX)
    f = [dydx, jeol, minX, i+1] #4번째 원소는 함수의 번호
    tmpf.append(f)

 

우리가 보통 아는 CHT 문제의 형태로 바꾸기 위해서 기울기는 내림차순, 절편은 오름차순 기준으로 정렬해주겠다.

tmpf.sort(key=lambda x:(-x[0], x[1]))

 

 

그리고 늘 그랬듯이 두 일차함수의 교점 구하는 함수를 정의해준다.

# 일차함수의 교차점 x좌표 찾는 함수
def cross(f, g):
    return round((g[1] - f[1])/(f[0] - g[0]), 5)

 

round 함수가 들어간 이유는 문제에서 선분들과 쿼리가 실수 형태로 주어지기 때문이다. (문제에서도 소수점 계산에 주의하라고 주어져있다)

 

이제 스택을 새로 정의하고 함수들을 하나하나씩 집어넣어서 Convex Hull을 관리해주도록 하자.

 

여기서 주의해야할 것이, 이 문제에서는 기울기가 같은 선분들이 있을 수 있다.

이 경우 교점이 없기 때문에 교점의 x좌표를 구할 때 ZeroDivisionError가 날 수도 있다.

따라서 선분을 하나하나 받아오면서 기울기가 같은 함수들은 y절편이 가장 작은 놈 하나만 가져오고 나머지는 버려줄 것이다.

 

for i in range(n):
    f = tmpf[i]
    if i >= 1 and f[0] == tmpf[i - 1][0]:
        continue

 

그리고는 보통의 CHT 처럼 해주면 된다.

 

for i in range(n):
    f = tmpf[i]
    if i >= 1 and f[0] == tmpf[i - 1][0]:
        continue

    if stack:
        tmp = cross(f, stack[-1])
        f[2] = tmp

    stack.append(f)

    # 그런데 쓸모없는 함수가 생길지도 모르니까
    while len(stack) >= 3 and cross(stack[-3], stack[-2]) > cross(stack[-2], stack[-1]):
        stack.pop(-2)
	# 교점 업데이트
    if len(stack) >= 2:
        stack[-1][2] = cross(stack[-1], stack[-2])

 

컨벡스 헐이 성공적으로 만들어졌다.

 

이제 주어진 쿼리들에 대해서 이분 탐색을 이용해서 선분들의 번호를 가져오면 된다.

 

from bisect import *
m = int(input())
for i in range(m):
    q = float(input())
    idx = bisect_right(stack, q, key = lambda x: x[2]) - 1
    print(stack[idx][3])

 

지난번 문제와 달리 bisect_right을 쓴 이유는,

어떠한 쿼리에서 선분이 두 개 이상 교차할 때 upper에서의 절편이 가장 작은 놈을 가져오라고 문제에서 조건을 걸어주었기 때문인데,

우리가 위 사진처럼 사진을 돌려주었을 때 우리가 찾고자 하는 선분은 가장 최근에 추가된 선분(스택상에서 오른쪽에 있는 선분)이기에 bisect_left 대신 bisect_right을 쓴다.

 

전체 코드는 다음과 같다.

 

# 일차함수의 교차점 x좌표 찾는 함수
def cross(f, g):
    return round((g[1] - f[1])/(f[0] - g[0]), 5)

maxX, minX = map(int, input().split())
n = int(input())

stack = [] #일차함수 관리해주는 스택
tmpf = []
for i in range(n):
    upperY, lowY = map(int, input().split())
    dydx = (upperY - lowY) / (maxX - minX)
    jeol = (lowY * maxX - upperY * minX) / (maxX - minX)
    f = [dydx, jeol, minX, i+1] #4번째 원소는 함수의 번호
    tmpf.append(f)

tmpf.sort(key=lambda x:(-x[0], x[1]))

for i in range(n):
    f = tmpf[i]
    if i >= 1 and f[0] == tmpf[i - 1][0]:
        continue

    if stack:
        tmp = cross(f, stack[-1])
        f[2] = tmp

    stack.append(f)
    
    # 그런데 쓸모없는 함수가 생길지도 모르니까
    while len(stack) >= 3 and cross(stack[-3], stack[-2]) > cross(stack[-2], stack[-1]):
        stack.pop(-2)

    if len(stack) >= 2:
        stack[-1][2] = cross(stack[-1], stack[-2])

from bisect import *
m = int(input())
for i in range(m):
    q = float(input())
    idx = bisect_right(stack, q, key = lambda x: x[2]) - 1
    print(stack[idx][3])

 

1트컷