Skip to content

14303: 【原4303】[JSOI2018] War

题目

题目描述

author: 血小板 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4303

Description

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

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

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

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

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

Input Format

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

接下来$n$ 行每行两个整数$x_i,y_i$表示第一个部落里的人的坐标。

接下来$m$行每行两个整数$x_i,y_i$表示第二个部落里的人的坐标。

接下来$q$行每行两个整数$dx_i,dy_i$表示一个迁徙方案。

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

Output Format

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

Sample Input

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

Sample Output

1
0
1

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!