| HNNU Freshman Competition Round 2 |
|---|
| Finished |
二维平面内有 $$$n$$$ 个不同的点 $$$P_1(x_1,y_1),P_2(x_2,y_2),\cdots,P_n(x_n,y_n)\ (\forall i \in [1,n],x_i,y_i \in Z)$$$。你需要找到三个整数 $$$i,j,k\ (1 \le i,j,k \le n)$$$ 使得 $$$i \not = j, i \not = k, j \not = k$$$ 且 $$$\angle P_iP_jP_k$$$ 是锐角$$$^*$$$,或报告无解。
*锐角是指严格大于0°而严格小于90°的角。
每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$,表示测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n\ (3 \le n \le 10^{5})$$$,表示点的数量。
接下来的 $$$n$$$ 行中,第 $$$i$$$ 行包含两个整数 $$$x_i,y_i\ (-10^9 \le x_i,y_i \le 10^9)$$$,表示第 $$$i$$$ 个点的坐标。保证 $$$n$$$ 个点坐标两两不同。
保证所有测试数据 $$$n$$$ 之和不超过 $$$10^5$$$。
对于每个测试用例,如果不存在解,输出一行一个整数 -1;否则输出一行 3 个整数 $$$i,j,k$$$ 满足题意。
如果有多种合法答案,你可以输出任意一种。
231 10 02 230 01 00 1
-11 2 3
对于第 1 个测试点:
$$$\angle P_1P_2P_3 = 0°,\angle P_2P_1P_3 = 180°,\angle P_1P_3P_2 = 0°$$$。
所以无解。
对于第 2 个测试点:
$$$\angle P_1P_2P_3 = 45°$$$。
| Name |
|---|


