[Silver III] 다중 일차 함수 - 26258

문제 링크

성능 요약

메모리: 41032 KB, 시간: 380 ms

분류

이분 탐색, 수학, 오프라인 쿼리, 두 포인터

문제 설명

2차원 좌표 평면에 점 $N$개가 주어진다. $i$번째 점의 위치는 $(x_i, y_i)$이고, $1 \leq i \lt N$인 모든 $i$에 대하여 $x_i \lt x_{i+1}$을 만족하며, 점 $i$와 점 $i + 1$을 잇는 일차 함수가 그려진다. 각각 구간 $(x_1, x_2), (x_2, x_3), \cdots, (x_{N-1}, x_N)$에서 정의되는 $N-1$ 개의 일차 함수를 합쳐 $F(x)$라고 정의하자.

예를 들어, 점이 $(0, 0)$,$(1,5)$,$(2,4)$,$(3,3)$,$(6,10)$으로 주어지면 그려지는 함수는 다음과 같다.

질의마다 실수 $k$가 주어지면 $x=k$에서 함수 $F(x)$의 증가/감소 여부를 구하자.

입력

첫 번째 줄에 점의 개수 $N$이 주어진다. $(2\leq N \leq 100\,000)$ 

두 번째 줄부터 $N$ 개의 줄에 걸쳐 점의 좌표 $x_i, y_i$가 공백으로 구분되어 주어진다. $(-10^9 \leq x_i, y_i \leq 10^9;\ x_i \lt x_{i + 1})$ 

$N+1$ 번째 줄에 질의의 개수 $Q$가 주어진다. $(1 \leq Q \leq 100\,000)$ 

$N+2$ 번째 줄부터 $Q$ 개의 줄에 걸쳐 질의의 정보 $k$가 주어진다. $(x_1 \lt k \lt x_N;\ k \neq x_i)$ 

$x_i, y_i$는 정수이고, $k$는 소수점 아래 최대 한 자리까지 주어진다.

출력

$k$가 속하는 일차 함수가 증가 함수면 $1$, 감소 함수면 $-1$, 둘 다 아니면 $0$을 각 줄마다 차례로 출력한다.

---

풀이

아이디어

biscet 모듈을 이용하여 풀이하기로 했다. 변화하는 $x$ 지점을 찾은 뒤, $y$ 값의 변화량의 양수, 음수 판단만 해준다. 이때 찾아준 bisect의 왼쪽, 오른쪽 값이 같다면 왼쪽 값을 1 낮춰준다. 이유는 $2.5$와 같이 두 수 사이의 값이 $x$ 값으로 들어가게 되면 탐색 범위가 나오지 않기 때문이다.

코드

import bisect
import sys
input = sys.stdin.readline
coord_x = []
coord_y = []
for i in range(int(input())):
    x, y = map(float, input().split())
    coord_x.append(x)
    coord_y.append(y)


for i in range(int(input())):
    c = float(input())
    left, right = bisect.bisect_left(coord_x, c), bisect.bisect_right(coord_x, c)
    if left == right:
        left -= 1
    if coord_y[right] - coord_y[left] > 0:
        print(1)
    elif coord_y[right] - coord_y[left] < 0:
        print(-1)
    else:
        print(0)

---

회고

아이디어에 기술했던 문제 때문에 조금 고민했던 문제이고, bisect 모듈에 대해 잘 알지 못해 발생한 일이다. 하지만 문제 풀이에 들어간 아이디어를 구상하는 시간이 짧았던것이 좋았던 것 같다.