만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

점 둘러싸기

시간 제한5초메모리 제한512 MB

요약
평면 위에서 서로 교차하지 않는 선분들이 주어질 때, 각 질의 점을 감싸는 다각형을 선분으로 만들 수 있는지 판별합니다.
난이도

보통10점 중 7점

유형
기하, 유니온 파인드, 정렬
정답자
아직 제출이 없습니다

문제

평면 위에 NN개의 점과 MM개의 선분이 있다. 각 선분은 두 점을 잇고, 선분끼리는 끝점을 제외하고 교차하지 않는다. 또한 QQ개의 질의 점이 주어진다. 각 질의 점에 대해, 주어진 선분 중 일부를 사용해 그 점을 둘러싸는 다각형을 만들 수 있는지 판단하라. 다각형이 볼록일 필요는 없다.

입력

첫 줄에 세 정수 NN (2≤N≤100,0002 \leq N \leq 100{,}000), MM (1≤M≤100,0001 \leq M \leq 100{,}000), QQ (1≤Q≤100,0001 \leq Q \leq 100{,}000)가 주어진다. 각각 점, 선분, 질의 점의 개수이다.

이어서 NN개의 줄에 ii번째 점의 좌표 xix_i, yiy_i (−100,000≤xi,yi≤100,000-100{,}000 \leq x_i, y_i \leq 100{,}000)가 주어진다. 모든 점은 서로 다르다.

다음 MM개의 줄에는 정수 aia_i, bib_i (1≤ai<bi≤N1 \leq a_i < b_i \leq N)가 주어지며, 이는 ii번째 선분이 aia_i번 점과 bib_i번 점을 잇는다는 뜻이다. 선분들은 끝점을 제외하고 교차하지 않는다.

마지막 QQ개의 줄에는 ii번째 질의 점의 좌표 qxiqx_i, qyiqy_i (−100,000≤qxi,qyi≤100,000-100{,}000 \leq qx_i, qy_i \leq 100{,}000)가 주어진다. 임의의 질의 점과 임의의 선분 사이의 거리는 10−410^{-4} 이상이다.

N M Q
x_1 y_1
...
x_N y_N
a_1 b_1
...
a_M b_M
qx_1 qy_1
...
qx_Q qy_Q

출력

QQ개의 줄을 출력한다. ii번째 줄에는 주어진 선분으로 질의 점 ii를 둘러싸는 다각형을 만들 수 있으면 "Yes", 그렇지 않으면 "No"를 출력한다.

예제3

  1. 예제 1

    입력
    4 5 3
-10 -10
10 -10
10 10
-10 10
1 2
1 3
1 4
2 3
3 4
-20 0
1 0
20 0
    예상 출력
    No
Yes
No

  2. 예제 2

    입력
    8 8 5
-20 -20
20 -20
20 20
-20 20
-10 -10
10 -10
10 10
-10 10
1 2
1 4
2 3
3 4
5 6
5 8
6 7
7 8
-25 0
-15 0
0 0
15 0
25 0
    예상 출력
    No
Yes
Yes
Yes
No

  3. 예제 3

    입력
    8 8 5
-20 -10
-10 -10
-10 10
-20 10
10 -10
20 -10
20 10
10 10
1 2
2 3
3 4
1 4
5 6
6 7
7 8
5 8
-30 0
-15 0
0 0
15 0
30 0
    예상 출력
    No
Yes
No
Yes
No