#P4557. [JSOI2018] 战争

    ID: 5102 远端评测题 1000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2018各省省选江苏向量凸包

[JSOI2018] 战争

题目描述

九条可怜是一个热爱读书的女孩子。

在她最近正在读的一本小说中,描述了两个敌对部落之间的故事。第一个部落有 nn 个人,第二个部落有 mm 个人,每一个人的位置可以抽象成二维平面上坐标为 (xi,yi)(x_i,y_i) 的点。

在这本书中,人们有很强的领地意识,对于平面上的任何一个点,如果它被三个来自同一部落的人形成的三角形(可能退化成一条线段)包含(包括边界),那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地中,那么这两个部落就会为了争夺这一个点而发生战争。

常年的征战让两个部落不堪重负,因此第二个部落的族长作出了一个英明的决定,他打算选择一个向量 (dx,dy)(dx,dy) ,让所有的族人都迁徙这个向量的距离,即所有第二阵营的人的坐标都变成 (xi+dx,yi+dy)(x_i+dx,y_i+dy)

现在他计划了 qq 个迁徙的备选方案,他想要你来帮忙对每一个迁徙方案,计算一下在完成了迁徙之后,两个部落之间还会不会因为争夺领地而发生战争。

输入格式

第一行输入三个整数 n,m,qn,m,q,表示两个部落里的人数以及迁徙的备选方案数。

接下来 nn 行每行两个整数 xi,yix_i,y_i​​ 表示第一个部落里的人的坐标。

接下来 mm 行每行两个整数 xi,yix_i,y_i​​ 表示第二个部落里的人的坐标。

接下来 qq 行每行两个整数 dxi,dyidx_i,dy_i​​ 表示一个迁徙方案。

输入数据保证所有人的坐标两两不同。

输出格式

对于每个迁徙方案,输出一行一个整数,00 表示不会发生冲突,11 表示会发生冲突。

4 4 3
0 0
1 0
0 1
1 1
-1 0
0 3
0 2
0 -1
0 0
2 3
0 -1
1
0
1

提示

样例 1 解释

下图为第一组方案中两个部落的私人领地,点 (0,0)(0,0) 同时属于两个部落,因此会发生战争。

0

下图为第二组方案中两个部落的私人领地,没有点同时属于两个部落,因此不会发生战争。

1

下图为第三组方案中两个部落的私人领地,点 (0,0)(0,0) 同时属于两个部落,因此会发生战争。

2

数据范围

对于 20%20\% 的数据, n,m5,q500n,m\le 5,q\le 500

对于 40%40\% 的数据, n,m50,q500n,m\le 50,q\le 500

对于 70%70\% 的数据, n,m104,q500n,m\le 10^4,q\le 500

对于 100%100\% 的数据, n,m105,q105n,m\le 10^5,q\le 10^5

对于 100%100\% 的数据,保证 108xi,yi,dxi,dyi108;n,m3-10^8\le x_i,y_i,dx_i,dy_i\le 10^8;n,m\ge 3 。所有人的坐标两两不同且对于每一个阵营,所有人都不全共线。