Codeforces Global Round 26 |
---|
Finished |
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:
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$$$.
351 12 53 34 25 461 13 31 22 13 1000019 8472 7-4 -3-3 63 1-5 21 -4-1 7
1 0 10
In the first test case, there is only one possible attack plan of shortest length, shown below.
In the second case, for example, you can never capture the tower at $$$(3, 10\,000)$$$.
Name |
---|