P8222 [WFOI - 02] I wanna escape the shadow (Shadow)

> Define adventure with death > > You are the shadow to my life The background suddenly became gloomy, but kid knows clearly: this is the darkest moment, and also the time right before dawn.

Now kid is inside a circle **with center $(0,0)$ and radius $r$**, and has learned a new operation `mklig(X,Y,Z)` to remove the darkness, described as follows. $X,Y,Z$ are three distinct points. Draw the rays $XY$ and $ZY$, and let the two rays intersect the circle at $d_1,d_2$. Then the region enclosed by the arc $d_1d_2$ and the segments $Yd_1$ and $Yd_2$ is lit up. Now there are some points inside the circle. Let $S_{光}$ be the total lit area when the circle radius is $r$. Now kid wants to know, when making $\lim\limits_{r \to \infty} \dfrac{S_{光}}{\pi r^2}$ (which can be understood as when $r$ goes to infinity) as large as possible, what is the minimum number of `mklig` operations needed. You only need to output the answer; leave the remaining operations to €€£! The testdata guarantees that no three points are collinear.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains a positive integer $n$. The next $n$ lines each contain two integers, representing the $x$ and $y$ coordinates of a point.

Output $T$ lines, each containing one integer, the answer.

- #### Sample Explanation  **This problem uses bundled Subtasks for testing.** - $\texttt{Subtask \#0 (30pts)}$: $n = 10^3$ and the data is random. - $\texttt{Subtask \#1 (30pts)}$: $n \le 5$. - $\texttt{Subtask \#2 (40pts)}$: $n \le 10^6$. Constraints: For each test point, it is guaranteed that $T \le 5$ and $\sum n \le 10^6$. The absolute value of each point’s coordinates does not exceed $10^9$. Translated by ChatGPT 5