logo AlgoBeat OnlineJudge
登录 注册

#214419. [NFLSPC #8] 轨道交通

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述


三叶虫非常喜欢建造地铁。他设计了 条线路,每条线路均有 个站点选址,用平面上的坐标表示。

为了丰富地铁体验,三叶虫决定每条线路都是一条线段!也就是说,对于对于每条线路,三叶虫仅会选择两个站点,在这两个站点之间连一条线段。为了最大化乘客换乘的麻烦程度,三叶虫要求建立的 条地铁之间两两交点个数最少。注意交点包含起点和终点站。请你规划一种合法的方案。


人话:给定二维平面上 种颜色的点各 个。要求在每种颜色中选出两个不同的点连一条线段,且所有 条线段两两交点个数最少。输出构造方案。

注意:如果两条线段共线,交点数定义为无穷大。所有无穷大认为相等。

输入格式

本题有多组测试数据,第一行一个正整数 表示数据组数,对于每一组测试数据:

第一行一个正整数 表示线路的数量。

接下来 行每行 个整数,其中第 个和第 个整数 标识了当前路线一个站点的坐标,且该站点的标号为

保证所有的站点坐标互不相同。

输出格式

对于每一组测试数据,输出 行每行两个正整数,依次表示每条线路连接的两个站点的标号。你只需要输出任意解。

样例

样例输入 1

1
2
5 0 0 8 10 8
0 4 10 4 5 12

样例输出 1

1 3
1 3

数据范围与提示

样例解释

图中蓝色和红色的点分别表示一号线和二号线的站点,蓝线和红线分别表示一号线和二号线选择的线路。

注意你只需要输出任意解,即

1 2
2 3

也是正确答案。

数据范围

子任务编号 分值 额外限制
1 30
2 20 存在一种排列这 个点的方案使得第 个点的坐标恰为
3
4 30

对于所有数据: