#P4982. [2017年湖南省队集训]第三题

    ID: 4082 传统题 1000ms 512MiB 尝试: 7 已通过: 3 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何Andrew 算法叉积构造与建模递归构造图构造数据结构普通并查集CF2500

[2017年湖南省队集训]第三题

不相交的双色树

题目描述

sl 在机房里玩一个平面连线游戏。平面上有 nn 个 A 类点和 mm 个 B 类点,两类点分别从 11 开始编号。

用 n−1n-1 条直线段把 A 类点连成一棵树,用 m−1m-1 条直线段把 B 类点连成一棵树。两棵树中任意两条边只能在它们共同的顶点相交。请给出一种合法连边方案,或报告无解。

输入格式

第一行两个整数 n,mn,m,分别表示两类点的数量。随后 nn 行每行两个整数,依次给出 A 类点的坐标。再随后 mm 行每行两个整数,依次给出 B 类点的坐标。

n+m≤3000n+m\le3000,坐标的绝对值不超过 10910^9。没有三点共线。

输出格式

如果无解,输出 GG!。

否则输出 n+m−2n+m-2 行。前 n−1n-1 行每行两个整数 a,ba,b,表示连接编号为 a,ba,b 的两个 A 类点。随后的 m−1m-1 行按相同格式输出 B 类树的边。

样例

3 2
1 0
0 1
2 3
0 0
1 1
1 3
2 3
1 2