← 返回题目列表

Codeforces · 2181/I

I. 灌溉联锁

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

两个灌溉合作社共享同一个肥沃的山谷。第一个合作社维护着分散在田地里的水泵;第二个负责监管周围山上的水库。每当两个合作社决定铺设一对新管道时,管道必须相交——在这样的交叉点上,他们可以安装一个接头阀。管道始终沿着一对不同的泵或一对不同的水箱之间的直线段。如果两条管道至少共享一个公共点,则它们相交(接触和重叠的管道被视为相交)。

您将获得笛卡尔平面上每个泵和每个水库的精确坐标。对于每个规划方案,确定第一个合作社是否可以选择两个不同的泵,第二个合作社是否可以选择两个不同的水库,以便两条直管相交。如果可能的话,报告这些泵和水库的指数;否则声明该项目无法实现。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 规划场景的数量。

对于每个规划场景:

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 第一个合作社管理的泵的数量。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^9$$$) - 泵 $$$i$$$ 的笛卡尔坐标。泵的位置是不同的。

下一行包含一个整数 $$$m$$$ ($$$2 \le m \le 10^5$$$) — 第二个合作社管理的水库数量。

接下来的 $$$m$$$ 行包含两个整数 $$$u_j$$$ 和 $$$v_j$$$ ($$$|u_j|, |v_j| \le 10^9$$$) - 水库 $$$j$$$ 的笛卡尔坐标。水库位置不同。

没有泵与任何水库共享其位置。

保证所有规划方案的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有规划方案的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个规划场景:

如果第一个合作社可以选择两台水泵,第二个合作社可以选择两个水库,使得连接每对水泵的直管段相交,则输出四个整数 $$$p_1$$$, $$$p_2$$$, $$$r_1$$$, $$$r_2$$$ ——两个所选水泵的索引 ($$$1 \le p_1, p_2 \le n$$$; $$$p_1 \ne p_2$$$) 和两个选定的水库 ($$$1 \le r_1, r_2 \le m$$$; $$$r_1 \ne r_2$$$)。

如果不可能有这样的交集,则输出$$$-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 4 1 2
-1
1 2 1 2

注意

规划场景 1规划场景 2规划场景 3