Codeforces Global Round 26 |
---|
Закончено |
В $$$n$$$ различных точках $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ существует $$$n$$$ башен, причем никакие три из них не являются коллинеарными, а четыре — конциклическими. Изначально вы владеете башнями $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, и хотите захватить их все. Для этого вы можете проделать следующую операцию любое количество раз:
План атаки — это последовательность выборов $$$R$$$ ($$$R_1, R_2, \ldots, R_k$$$) в рамках вышеописанных операций, после которых вы захватываете все башни. Обратите внимание, что два плана атаки считаются различными, только если они отличаются выбором $$$R$$$ в некоторой операции; в частности, два плана атаки с одинаковым выбором $$$R$$$, но разными выборами $$$P$$$ и $$$Q$$$ считаются одинаковыми.
Подсчитайте количество планов атаки минимальной длины. Обратите внимание, что захватить все башни может быть невозможно, и в этом случае ответ будет равен $$$0$$$.
Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 250$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 100$$$) — количество башен.
В $$$i$$$-й из следующих $$$n$$$ строк содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^4 \leq x_i, y_i \leq 10^4$$$) — местоположение $$$i$$$-й башни. Изначально вы владеете башнями $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$.
Все башни находятся в разных местах, никакие три башни не коллинеарны и никакие четыре башни не лежат на одной окружности.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите одно целое число — количество планов атаки минимальной длины, после которых вы захватите все башни, по модулю $$$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
В первом наборе входных данных существует только один возможный план атаки наименьшей длины, показанный ниже.
Во втором наборе входных данных, например, вы никогда не сможете захватить башню в точке $$$(3, 10\,000)$$$.
Название |
---|