eolymp
bolt
Try our new interface for solving problems
Məsələlər

Созвездия

Созвездия

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Вадим увлекается астрономией и даже ходит в астрономический кружок. Недавно на кружке он узнал о созвездиях. Это понятие его очень заинтересовало, поэтому, придя домой вечером, он софотографировал звездное небо с помощью телескопа и стал искать созвездия на получившемся снимке.

Для того, чтобы выделять созвездия, он придумал простое правило - звезда A находится в одном созвездии со всеми теми звездами, изображения которых на снимке находятся от ее изображения "не слишком далеко". Пусть расстояние от изображения звезды A до ближайшего изображения звезды равно d. Тогда в одно созвездие с A Вадим отнесет все звезды, изображения которых находятся на расстоянии не более k·d, где k - некоторое целое число, выбранное Вадимом заранее.

Это правило он применяет следующим образом. Звезды A и B находятся, по мнению Вадима, в одном созвездии, если существует такая последовательность звезд A = u_1, u_2, ..., u_l = B, что для любых двух соседних звезд u_i и u_{i+1} в этой последовательности выполняется хотя бы одно условие из двух:

  • расстояние между их изображениями не превосходит k·md(u_i) (как md(X) будем обозначать расстояние от изображения звезды X до ближайшего изображения другой звезды);

  • расстояние между их изображениями не превосходит k·md(u_{i+1}).

При этом Вадим обязательно относит две звезды к одному созвездию, если существует указанная последовательность звезд.

Ваша задача состоит в том, чтобы написать программу, которая по информации о координатах изображений звезд на снимке, разобъет их на созвездия по методу Вадима.

Giriş verilənləri

Первая строка входного файла содержит два целых числа: n - количество звезд на снимке (2n5000) и k (1k10). Каждая из последующих n строк содержит по 2 числа - x_i и y_i - координаты изображения очередной звезды (|x_i|, |y_i| ≤ 10^5). Изображения всех звезд находятся в различных точках.

Çıxış verilənləri

В выходной файл выведите m - количество созвездий. В последующих m строках выведите описания созвездий. Описания каждого созвездия должно содержать число n_i - количество звезд в очередном созвездии, и n_i чисел - номера этих звезд. Звезды нумеруются натуральными числами от 1 до n в том порядке, в котором они перечислены во входном файле.

Nümunə

Giriş verilənləri #1
8 1
0 0
1 1
1 0
0 1
2 2
2 3
3 2
3 3
Çıxış verilənləri #1
2
4 1 2 3 4
4 5 6 7 8