← 返回题目列表

AtCoder · icpc2015summer_day4_e

E. 包含点

中文机器翻译题面 查看原题

问题陈述

$xy$ 平面上有 $N$ 个点和 $M$ 个线段。 每条线段连接其中两个点,并且除了端点之外,它们不会彼此相交。 您还将获得 $Q$ 积分作为查询。 您的任务是确定对于每个查询点是否可以使用某些给定线段创建包围查询点的多边形。 请注意,多边形不一定是凸多边形。


输入

每个输入的格式如下。

$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$

第一行包含三个整数 $N$ ($2 \leq N \leq 100{,}000$)、$M$ ($1 \leq M \leq 100{,}000$) 和 $Q$ ($1 \leq Q \leq 100{,}000$), 分别表示点的数量、段的数量和查询的数量。 以下 $N$ 行中的每一行都包含两个整数 $x_i$ 和 $y_i$ ($-100{,}000 \leq x_i, y_i \leq 100{,}000$),即第 $i$ 个点的坐标。 这些点保证是不同的,即当 $i \neq j$ 时,$(x_i, y_i) \neq (x_j, y_j)$。 接下来的$M$行中的每一行都包含两个整数$a_i$和$b_i$ ($1 \leq a_i \lt b_i \leq N$),表示第$i$段连接第$a_i$点和第$b_i$点。 假设这些线段除了端点之外不互相相交。 以下每行 $Q$ 包含两个整数 $qx_i$ 和 $qy_i$ ($-100{,}000 \leq qx_i, qy_i \leq 100{,}000$),即第 $i$ 个查询点的坐标。

您可以假设,对于任何一对查询点和线段,它们之间的距离至少为 $10^{-4}$。

输出

输出应包含 $Q$ 行。 打印“Yes" 如果存在包含第 $i$ 个查询点的多边形,则在第 $i$ 行上。 否则打印“No" 在第 $i$ 行。


示例输入 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

样本输入 1 的输出

No
Yes
No

示例输入 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

样本输入 2 的输出

No
Yes
Yes
Yes
No

示例输入 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

样本输入 3 的输出

No
Yes
No
Yes
No