시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 373 | 125 | 96 | 35.165% |
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$을 각 줄마다 차례로 출력한다.
5 0 0 1 5 2 5 3 3 6 10 3 2.5 4 1.5
-1 1 0
주어진 예제는 지문의 사진과 같은 함수이다.
Contest > SW마에스트로 > 제13기 알고리즘 대회 B번