#PQJ165x523. QOJ 165_523
QOJ 165_523
部落战争 (war) 部落战争 (war) 【问题描述】 九条可怜是一个热爱读书的女孩子。 在她最近正在读的一本小说中,描述了两个敌对部落之间的故事。第一个部 落有𝑛个人,第二个部落有𝑚个人,每一个人的位置可以抽象成二维平面上坐标 为(𝑥%, 𝑦%)的点。 在这本书中,人们有很强的领地意识,对于平面上的任何一个点,如果它被 三个来自同一部落的人形成的三角形(可能退化成一条线段)包含(包括边界), 那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地 中,那么这两个部落就会为了争夺这一个点而发生战争。 常年的征战让两个部落不堪重负,因此第二个部落的族长作出了一个英明的 决定,他打算选择一个向量 (𝑑𝑥, 𝑑𝑦),让所有的族人都迁徙这个向量的距离,即 所有第二阵营的人的坐标都变成(𝑥% + 𝑑𝑥, 𝑦% + 𝑑𝑦)。 现在他计划了𝑞个迁徙的备选方案,他想要你来帮忙对每一个迁徙方案,计 算一下在完成了迁徙之后,两个部落之间还会不会因为争夺领地而发生战争。 【输入格式】 第一行输入三个整数𝑛, 𝑚, 𝑞,表示两个部落里的人数以及迁徙的备选方案 数。 接下来𝑛行每行两个整数𝑥%, 𝑦%表示第一个部落里的人的坐标。 接下来𝑚行每行两个整数𝑥%, 𝑦%表示第二个部落里的人的坐标。 接下来𝑞行每行两个整数𝑑𝑥%, 𝑑𝑦%表示一个迁徙方案。 【输出格式】 对于每个迁徙方案,输出一行一个整数,0 表示不会发生冲突,1 表示会发 生冲突。 【样例输入】 4 4 3
部落战争 (war) 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 【样例说明】 下图为第一组方案中两个部落的私人领地,点(0,0)同时属于两个部落,因此 会发生战争。
下图为第二组方案中两个部落的私人领地,没有点同时属于两个部落,因此 不会发生战争。
部落战争 (war)
下图为第三组方案中两个部落的私人领地,点(0,0)同时属于两个部落,因此 会发生战争。
【数据规模】 对于20%的数据,𝑛, 𝑚≤5, 𝑞≤500。 对于40%的数据,𝑛, 𝑚≤50, 𝑞≤500。 对于70%的数据,𝑛, 𝑚≤100, 𝑞≤500。 对于100%的数据,𝑛, 𝑚≤101, 𝑞≤101。 对于100%的数据,保证−103 ≤𝑥%, 𝑦%, 𝑑𝑥%, 𝑑𝑦% ≤103, 𝑛, 𝑚≥3。所有人的坐 标两两不同且对于每一个阵营,所有人都不全共线。