409553: GYM103630 E Рудольф и звезды

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Рудольф и звездыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольф решил освежить свои познания в астрономии и скачал новейшую карту звездного неба. Он настолько увлекся ее изучением, что не заметил, как пролетело $$$12$$$ часов. За это время он умудрился запомнить абсолютно все созвездия. Для этого он воспользовался небезызвестной техникой «дворец памяти». Ну а поскольку он все же математик, то его дворец памяти представляет собой координатную плоскость. На этой плоскости Рудольф и разместил все звезды, $$$i$$$-я из которых теперь имеет координаты $$$(X_i, Y_i)$$$.

Довольный собой, Рудольф решил проверить, насколько хорошо сработала эта техника. Поздней ночью он вышел на улицу и взглянул на небо. И тут он внезапно обнаружил там кроме звезд еще и луну. Рудольф быстро понял, что далеко не все созвездия он может найти, потому что они «спрятались» за луной. Чтобы актуализировать информацию в своей голове, он решил поместить в свой координатный дворец памяти луну, которая формально представляет собой круг радиуса $$$R$$$ с центром в точке $$$(X_0,Y_0)$$$. Ну а чтобы не засорять память лишней информацией, он решил забыть координаты звезд, принадлежащих тем созвездиям, которые полностью перекрыты луной.

Помогите Рудольфу определить, какие созвездия нужно забыть.

Входные данные

Первая строка содержит три целых числа $$$X_0, Y_0, R$$$ ($$$-10^9 \le X_0, Y_0, R \le 10^9$$$) — координаты и радиус луны в системе координат Рудольфа.

Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество звезд.

Далее следует $$$N$$$ строк — описания звезд.

Каждая строка описания содержит пару целых чисел $$$X_i, Y_i$$$ ($$$-10^9 \le X_i, Y_i \le 10^9$$$) — координаты звезды. Далее следует непустая строка из строчных букв английского алфавита — наименование созвездия, которому принадлежит звезда. Длина наименования не превышает $$$20$$$.

Выходные данные

В первой строке выведите целое число $$$K$$$ — количество созвездий, которые «спрятались» за луной.

Во второй строке выведите через пробел $$$K$$$ наименований созвездий, которые «спрятались» за луной, в лексикографическом порядке.

ПримерВходные данные
0 0 100
7
1 1 hydra
2 0 pegasus
-1 3 hydra
0 0 hercules
-200 0 pegasus
100 0 hydra
10 20 hercules
Выходные данные
2
hercules hydra 

加入题单

上一题 下一题 算法标签: