Воздушный удар
Генерал Джи командует военной базой и только что получил тревожные новости от одного из своих шпионов: враг готовит ракетный удар с воздуха. На базе установлены две магнитные башни. Когда они активированы и получают достаточное количество энергии, каждая из башен создает мощный горизонтальный магнитный диск. Если ракета проходит через этот диск, она отклоняется от базы.
Несмотря на то, что эти башни кажутся отличным средством воздушной обороны, есть проблема: площадь диска, создаваемого башней, пропорциональна количеству получаемой энергии. У базы достаточно электростанций для генерации определенного количества энергии, которая должна быть распределена между двумя башнями. Это означает, что суммарная площадь двух дисков, создаваемых башнями, не должна превышать общего количества энергии, генерируемой электростанциями. К счастью, шпион смог узнать точные координаты цели приближающихся ракет и сообщил их генералу Джи. Генералу нужна ваша помощь в распределении энергии между двумя магнитными башнями, чтобы минимизировать количество ракет, которые не будут отклонены магнитными башнями и, следовательно, попадут в базу. Вы можете предположить следующее:
Башни имеют разную высоту, и поэтому нет проблем, связанных с взаимным влиянием магнитных дисков.
Ракета отклонится, если она пройдет через магнитный диск башни или даже если просто коснется его границы.
Ракета, попавшая в башню (приземлившаяся точно на ее местоположение), отклонится, даже если башня не получила никакой энергии.
Все приближающиеся ракеты упадут одновременно в один и тот же момент; следовательно, не будет времени для перераспределения энергии между двумя башнями во время удара.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай задается на N+2 строках. Первая строка содержит целое число (1 ≤ N ≤ 1,000), представляющее количество ракет. Вторая строка содержит 5 вещественных чисел X_1, Y_1, X_2, Y_2 и T: (X_1, Y_1) — это координаты первой башни, (X_2, Y_2) — координаты второй башни, и 0 ≤ T — это общее количество энергии, генерируемой электростанциями (общая площадь двух магнитных дисков). Каждая из оставшихся N строк содержит два вещественных числа, представляющих координаты приземления ракеты.
Абсолютное значение всех данных вещественных чисел не превышает 100 и может включать десятичную точку, за которой следует до 3 цифр. Любые два последовательных числа в одной строке разделены одним или несколькими пробелами. Между тестовыми случаями могут появляться нулевые или более пустых строк.
Последняя строка входного файла состоит из одного нуля.
Выходные данные
Для каждого тестового случая выведите следующую строку:
k. M
Где k — номер тестового случая (начиная с единицы), а M — минимальное количество ракет, которые НЕ будут отклонены при наилучшем распределении энергии между двумя башнями. Используйте π = 3.141.
Примечание: Перед M стоит пробел.