시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 64 MB | 36 | 10 | 8 | 34.783% |
Professor Zhang draws $n$ points on the plane which are conveniently labeled by $1, 2, \ldots, n$. The $i$-th point is at $(x_i, y_i)$. Professor Zhang wants to know the number of best sets. As the value could be very large, print it modulo $10^9 + 7$.
A set $P$ ($P$ contains the labels of the points) is called a best set if and only if there is at least one best pair in $P$. Two numbers $u$ and $v$ $(u, v \in P, u \ne v)$ are called a best pair if for every $w \in P$, $f(u, v) \ge g(u, v, w)$, where $f(u, v) = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}$ and $g(u, v, w) = \frac{f(u, v) + f(v, w) + f(w, u)}{2}$.
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:
The first line contains an integer $n$ $(1 \le n \le 1000)$: the number of points.
Each of the following $n$ lines contains two integers $x_i$ and $y_i$ $(-10^9 \le x_i, y_i \le 10^9)$: coordinates of the $i$-th point.
There are no more than $250$ test cases, and the sum of $n$ in all the test cases is at most $40\,000$.
For each test case, output a single integer: the number of best sets modulo $10^9 + 7$.
3 3 1 1 1 1 1 1 3 0 0 0 1 1 0 1 0 0
4 3 0