codeforces#P1984H. Tower Capturing
Tower Capturing
Description
There are $n$ towers at $n$ distinct points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$, such that no three are collinear and no four are concyclic. Initially, you own towers $(x_1, y_1)$ and $(x_2, y_2)$, and you want to capture all of them. To do this, you can do the following operation any number of times:
- Pick two towers $P$ and $Q$ you own and one tower $R$ you don't own, such that the circle through $P$, $Q$, and $R$ contains all $n$ towers inside of it.
- Afterwards, capture all towers in or on triangle $\triangle PQR$, including $R$ itself.
Count the number of attack plans of minimal length. Note that it might not be possible to capture all towers, in which case the answer is $0$.
Since the answer may be large, output it modulo $998\,244\,353$.
The first line contains a single integer $t$ ($1 \leq t \leq 250$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($4 \leq n \leq 100$) — the number of towers.
The $i$-th of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^4 \leq x_i, y_i \leq 10^4$) — the location of the $i$-th tower. Initially, you own towers $(x_1, y_1)$ and $(x_2, y_2)$.
All towers are at distinct locations, no three towers are collinear, and no four towers are concyclic.
The sum of $n$ over all test cases does not exceed $1000$.
For each test case, output a single integer — the number of attack plans of minimal length after which you capture all towers, modulo $998\,244\,353$.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 250$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($4 \leq n \leq 100$) — the number of towers.
The $i$-th of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^4 \leq x_i, y_i \leq 10^4$) — the location of the $i$-th tower. Initially, you own towers $(x_1, y_1)$ and $(x_2, y_2)$.
All towers are at distinct locations, no three towers are collinear, and no four towers are concyclic.
The sum of $n$ over all test cases does not exceed $1000$.
Output
For each test case, output a single integer — the number of attack plans of minimal length after which you capture all towers, modulo $998\,244\,353$.
3
5
1 1
2 5
3 3
4 2
5 4
6
1 1
3 3
1 2
2 1
3 10000
19 84
7
2 7
-4 -3
-3 6
3 1
-5 2
1 -4
-1 7
1
0
10
Note
In the first test case, there is only one possible attack plan of shortest length, shown below.
- Use the operation with $P =$ tower $1$, $Q =$ tower $2$, and $R =$ tower $5$. The circle through these three towers contains all towers inside of it, and as a result towers $3$ and $5$ are captured.
- Use the operation with $P =$ tower $5$, $Q =$ tower $1$, and $R =$ tower $4$. The circle through these three towers contains all towers inside of it, and as a result tower $4$ is captured.
In the second case, for example, you can never capture the tower at $(3, 10\,000)$.