CFCF2181I.Irrigation Interlock
NOI/NOI+/CTSC
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
两个灌溉合作社共用一个肥沃的山谷。第一家合作社在田野间维护着若干台泵站;第二家合作社负责监督周围山丘上的水库。每当两个合作社决定分别铺设两根新管道时,这两根管道必须相交——在交点处可以安装一个联合阀门。每根管道总是沿着连接两个不同泵站或两个不同水库的直线段。两根管道若有至少一个公共点,则认为它们相交(无论仅接触还是重合,都算作相交)。
已知每个泵站和每个水库在平面直角坐标系上的精确坐标。对于每个规划方案,判断第一合作社是否能够选出两个不同的泵站、第二合作社是否能够选出两个不同的水库,使得各自连成的两条直线管道相交。如果可能,输出所选泵站和水库的编号;否则,说明该工程无法实现。
输入格式
第一行包含一个整数 t(1≤t≤105),表示规划方案的数量。
对于每个规划方案:
第一行包含一个整数 n(2≤n≤105),表示第一合作社管理的泵站数量。
接下来的 n 行,每行包含两个整数 xi 和 yi(∣xi∣,∣yi∣≤109),表示第 i 个泵站的坐标。所有泵站的位置各不相同。
接下来一行包含一个整数 m(2≤m≤105),表示第二合作社管理的水库数量。
接下来的 m 行,每行包含两个整数 uj 和 vj(∣uj∣,∣vj∣≤109),表示第 j 个水库的坐标。所有水库的位置各不相同。
任意一个泵站的位置都不会与任意一个水库的位置重合。
保证所有规划方案中 n 的总和不超过 2×105,所有 m 的总和也不超过 2×105。
输出格式
对于每个规划方案:
如果第一个合作社能选出两个泵站、第二个合作社能选出两个水库,使得各自连线的直线段相交,则输出四个整数 p1、p2、r1、r2——表示所选两个泵站(1≤p1,p2≤n,p1=p2)和所选两个水库(1≤r1,r2≤m,r1=r2)的编号。
如果不存在这样的选择,使得直线相交,则输出 −1。
如有多种方案,输出任意一种均可。
输入输出样例
输入#1
3 4 0 0 4 0 3 3 1 3 5 -1 1 5 1 2 -1 2 4 6 3 4 0 0 1 0 0 1 1 1 4 5 5 6 5 5 6 6 6 3 0 0 4 0 0 2 3 4 -2 4 2 6 1
输出#1
1 4 1 2 -1 1 2 1 2
说明/提示



规划方案 1
规划方案 2
规划方案 3
