每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数,每组测试数据描述如下:第一行输入一个整数 ,表示点的数量。此后 行,第 行输入两个整数 ,表示第 个点的坐标。保证 个点坐标两两不同。除此之外,保证单个测试文件的 之和不超过 。
对于每一组测试数据,新起一行。如果不存在解,输出 ;否则输出四个整数 ,表示四个点的编号。如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
2 4 0 0 9 0 0 9 9 9 4 0 0 9 0 0 9 1 1
1 2 4 3 -1
对于第一组测试数据,如下图所示。 和 和 和 都是满足条件的解。对于第二组测试数据,如下图所示,显然不存在满足条件的凸四边形。