Задача №115401. Лягушки на болоте
В Сочи при подготовке Олимпиады-2014 была завезена самшитовая огнёвка (небольшая бабочка с Дальнего Востока). Она уничтожила самшитовую рощу, поэтому древесным лягушкам теперь приходится жить на болоте. Но они сохранили способность после прыжка менять свой цвет с зелёного на коричневый и наоборот.
Болото представляет собой плоскость, в некоторых точках которой располагаются кочки. Размером кочек можно пренебречь и считать их точками на плоскости. За один прыжок лягушка может перепрыгнуть с кочки, на которой она находится, на любую другую кочку, которая находится от неё на расстоянии не более \(r\). После каждого прыжка цвет лягушки меняется на противоположный. Прыгать на месте лягушка не умеет.
Вам необходимо для каждой стартовой кочки лягушки от \(1\) до \(n\) определить, может ли она, совершив некоторое количество прыжков, вернуться на стартовую кочку, поменяв при этом свой цвет.
Первая строка содержит два целых числа \(n\) и \(r\) (\(2 \le n \le 10^5\), \( 1 \le r \le 10^9\)) — число кочек на болоте и расстояние, на которое прыгает лягушка.
Каждая из следующих \(n\) строк описывает расположение кочек. В \(i\)-й из них содержатся два целых числа \(x_i\) и \(y_i\) (\(0 \le x_i, y_i \le 5 \cdot 10^8\)) — координаты \(i\)-й кочки.
Никакие две кочки не располагаются в одной точке.
Выведите строку, состоящую из \(n\) символов. Если лягушка, стартовав с кочки \(i\), может вернуться на неё, имея противоположный цвет, \(i\)-й символ должен быть « 1 », а иначе — « 0 ».
| Подзадача | Баллы | Дополнительные ограничения | Необх. подзадачи |
| 1 | 10 | \(n \le 3\) | |
| 2 | 20 | \(n \le 200\) | У, 1 |
| 3 | 6 | \(n \le 1~000\) | У, 1, 2 |
| 4 | 9 | \(n \le 10~000\) | У, 1–3 |
| 5 | 16 | \(y_i = 0\) | |
| 6 | 5 | \(r \le 2\) | |
| 7 | 5 | \(r \le 4\) | 6 |
| 8 | 5 | \(r \le 10\) | У, 6, 7 |
| 9 | 12 | \((x_i - x_j)^2 + (y_i - y_j)^2 \ge \frac{r^2}{4}\), \(i \ne j\) | У, 6 |
| 10 | 12 | У, 1–9 |
Прыжки, которые позволяют лягушке поменять цвет, начав с первой кочки, показаны на рисунке ниже.
6 5 4 1 4 4 1 5 5 9 9 6 10 2
111000