Республиканская олимпиада по информатике 2008 год

Задача H. Звездное небо

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайт

Денис Назаров, Уфа

Ясным зимним вечером член жюри республиканской олимпиады по информатике Иван Васильевич, не торопясь, шел домой. Взгляд его время от времени блуждал по безоблачному ночному небу, которое поражало своей неземной красотой. Придя домой, он решил составить карту звездного неба таким образом, чтобы звезды были расположены на координатной плоскости только в точках с целочисленными координатами. Единицей длины и ширины на координатной плоскости решено было выбрать 1 световой год. При этом Иван Васильевич захотел поделить звезды на созвездия по следующему правилу: звезда принадлежит некоторому созвездию, если в этом созвездии найдется еще хотя бы одна такая звезда, расстояние до которой на координатной плоскости не больше $К$ световых лет. Звезда не может принадлежать двум разным созвездиям сразу, и любое созвездие содержит хотя бы одну звезду. После этого Иван Васильевич решил определить центр созвездия следующим образом: центром созвездия назовем такую звезду, при удалении которой из карты, созвездие распадется на несколько созвездий. У одного созвездия может быть несколько центров. Созвездия, которые состоят из 2 и менее звезд, по определению не могут иметь центров. Помогите Ивану Васильевичу определить центры всех созвездий.

Формат входного файла

Входной файл содержит координаты всех звезд (xi,yi). Координаты звезд попарно различны. Количество звезд меньше 3000, но больше 1. Координаты звезд – целые числа, по абсолютному значению меньшие 214. В последней строке расположено единственное целое неотрицательное число $K$, меньшее $10^9$.

Формат выходного файла

Ваша программа должна вывести в выходной файл два целых числа – количество созвездий и общее количество их центров на звездной карте.

Пример:

Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1