CirnoNine 找凸四边形
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}二维平面内有 n 个不同的整数点 P_1(x_1,y_1)P_2(x_2,y_2)、……、P_n(x_n,y_n)(即 \forall i \in [1,n];\, x_i,y_i \in \Bbb Z)。
\hspace{15pt}CirnoNine 需要你帮忙找到四个互不相同的整数 a,b,c,d\left(1 \le a,b,c,d \le n\right) 满足以下条件:
\hspace{23pt}\bullet\,P_a,P_b,P_c,P_d 依次连接可以组成凸四边形(即四个内角都严格小于 180°)。
\hspace{23pt}\bullet\,P_a,P_b,P_c,P_d 是四边形上逆时针顺序的点。
\hspace{15pt}如果无法找到满足条件的四个整数,你也可以告诉她不存在。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 2 \times 10^5\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n\left(4 \le n \le 5 \times 10^{5}\right),表示点的数量。
\hspace{15pt}此后 n 行,第 i 行输入两个整数 x_i,y_i\left(-10^9 \le x_i,y_i \le 10^9\right),表示第 i 个点的坐标。保证 n 个点坐标两两不同。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 5\times10^5

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行。如果不存在解,输出 -1;否则输出四个整数 a,b,c,d,表示四个点的编号。

\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

复制
2
4
0 0
9 0
0 9
9 9
4
0 0
9 0
0 9
1 1

输出

复制
1 2 4 3
-1

说明

\hspace{15pt}对于第一组测试数据,如下图所示。1,2,4,32,4,3,14,3,1,23,1,2,4 都是满足条件的解。



\hspace{15pt}对于第二组测试数据,如下图所示,显然不存在满足条件的凸四边形。