#P18677. Classical Minimization Problem
Classical Minimization Problem
Classical Minimization Problem
给定平面上 个互不相同的点。第 个点的整数坐标为 。
如果两个点 满足 或者 ,则称它们为一对友好点。
请把这些点分成 对,每个点恰好属于一对,并使这些配对中友好点对的数量最少。
输入格式
每份输入包含多组测试。第一行给出测试组数 ()。随后依次给出各组。
每组第一行包含一个整数 ()。
接下来 行,第 行给出两个整数 (),表示第 个点的坐标。保证同一组内所有点互不相同。
保证所有测试组的 之和不超过 。
输出格式
对每组测试,先输出一个非负整数 ,表示能够达到的最少友好点对数。
接下来输出 行,第 行包含两个整数 ,表示将第 个点和第 个点配成一对(,)。
从 到 的每个编号必须在全部 中恰好出现一次。满足两点横坐标相等或纵坐标相等的配对数量,必须恰好等于你输出的 ,且 必须最小。
有多个最优配对方案时,可以输出任意一种。
样例输入 1
3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3
样例输出 1
0
3 2
4 1
2
2 1
4 3
0
4 3
2 1