Məsələlər
False figures
False figures
Эта задача является валидатором тестов к предыдущей задаче. Самое сложное уже проверили, вам предлагается всего лишь проверить вложенность кругов.
Представим таблицу \{\textbf{a_ij}\} из \textbf{1000} строк и \textbf{1000} столбцов. Дано \textbf{Q} запросов вида:
\textbf{i_k j_k r_k}, \textbf{1} ≤ \textbf{k} ≤ \textbf{Q}
Каждый из них определяет область из элементов таблицы \{\textbf{a_ij}\} таких, что \textbf{(i-i_k)^2 + (j-j_k)^2} ≤ \textbf{r^2_k}.
Для удобства будем называть эту область кругом с центром в ячейке (\textbf{i_k}, \textbf{j_k}) и радиусом \textbf{r_k}.
Пара запросов \textbf{k} и \textbf{l} (\textbf{k} < \textbf{l}) считается невалидной, если круги \textbf{k} и \textbf{l} имеют общие ячейки, и существует круг \textbf{t}: \textbf{k} < \textbf{t} ≤ \textbf{l}, который не содержится в круге \textbf{k}. Круги различных запросов могут совпадать.
Определить, есть ли среди запросов хотя бы одна невалидная пара.
\InputFile
В первой строке число \textbf{Q} --- количество запросов. Далее в \textbf{Q} строках описаны запросы по три целых числа в каждой строке \textbf{i_k}, \textbf{j_k}, \textbf{r_k} --- номера строки и столбца центральной ячейки и радиус круга. Ячейки нумеруются с \textbf{1}.
\OutputFile
Если есть хотя бы одна невалидная пара запросов, вывести номера этих запросов в произвольном порядке. Если таких пар много, разрешается вывести любую из них. Если невалидных пар нет, вывести "\textbf{Ok}".
\textbf{Ограничения}
\textbf{1} ≤ \textbf{Q} ≤ \textbf{10^6}
\textbf{1 + r_k} ≤ \textbf{i_k} ≤ \textbf{1000-r_k}
\textbf{1 + r_k} ≤ \textbf{j_k} ≤ \textbf{1000-r_k}
\textbf{0} ≤ \textbf{r_k} < \textbf{500}
Giriş verilənləri #1
6 10 10 5 10 10 4 5 10 0 10 5 0 10 15 0 15 10 0
Çıxış verilənləri #1
Ok