21065번 - Friendship Circles 다국어

Let $p_0, p_1, \dots, p_{n-1}$ be $n$ points in the plane. We say that two points are friends if one can draw a circle that contains both points in its interior and all the other $n-2$ points in its exterior. Print the indices of the points that are friends with $p_0$.

It is guaranteed that there is no circumference containing $p_0$ and three or more other points. It is also guaranteed that there is no line containing $p_0$ and two or more other points.

The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 10^4$).

Each test case starts with a line containing an integer $n$ ($2 \leq n \leq 10^5$), the number of points. It is followed by $n$ lines, each one containing two integers $x_i$ and $y_i$ ($-10^{9} \leq x_i, y_i \leq 10^{9}$): the coordinates of the $i$-th point.

The tests are not explicitly targeting precision issues. In particular, it is guaranteed that, if we moved $p_0$ by a distance of at most $10^{-6}$ units in any direction, the answer would remain the same.

The total number of points in all test cases does not exceed $10^5$.

For each test case, print a line containing one integer $m$, the number of friends of $p_0$, followed by $m$ integers: the indices of the friends of $p_0$ in lexicographical order.