시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3731259635.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$을 각 줄마다 차례로 출력한다.

예제 입력 1

5
0 0
1 5
2 5
3 3
6 10
3
2.5
4
1.5

예제 출력 1

-1
1
0

주어진 예제는 지문의 사진과 같은 함수이다.

출처

Contest > SW마에스트로 > 제13기 알고리즘 대회 B번