Background

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.

Problem Description

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.

Input Format

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 Format

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

1
3
0 0
0 2
-1 1

3

Hint

• 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