eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Атака на гигантского n-минога

Атака на гигантского n-минога

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Пиратский корабль подвергается нападению гигантского n-минога^1. n щупалец и голова существа пронзили палубу, сея хаос на корабле. В попытке остановить существо в полном уничтожении корабля, капитан стреляет в сторону головы существа. К сожалению, его быстро отбрасывает назад одним из щупалец. Капитан понимает, что он не может атаковать голову n-минога до тех пор, пока тот может свободно двигать своими щупальцами.

К счастью, капитан не один на корабле. На палубе имеется p (pn) пиратов, готовых выполнять приказы капитана. Капитан придумывает следующий план. Если каждое щупальце будет атаковано одним из пиратов, то он сможет свободно подобраться к голове существа и прикончить ее. Ради своей безопасности капитан начнет действовать только после того как каждое щупальце будет атаковано пиратами. Когда капитан достигает головы, он может мгновенно убить существо. Капитану следует решить, каких пиратов к каким щупальцам следует отправить, чтобы можно было убить существо как можно быстрее. Так как подобная задача регулярно возникает у пиратов, капитан просит Вас написать программу для ее решения.

____________

^1 - n-миног - это осьминог с n щупальцами.

Вхідні дані

Первая строка содержит количество тестов. Каждый тест имеет следующий формат:

  • одна строка с целыми числами n и p (1 n p 100) - количество щупалец у n-минога и количество пиратов (не включая капитана).

  • строка с тремя целыми числами x_c, y_c и v_c - координаты капитана и его скорость.

  • p строк, каждая из которых содержит три целых числа x_i, y_{i }и v_i - координаты и скорость каждого пирата.

  • строка с двумя целыми числами x_h и y_h - координаты головы n-минога.

  • n строк, каждая из которых содержит два целых числа x_j и y_j - координаты каждого щупальца.

Все координаты удовлетворяют неравенствам 0 x, y 10000. Все скорости удовлетворяют 1 v 100.

Капитан, пираты, голова и щупальца считаются точками (то есть не имеют размера). Все их положения различны.

Капитан и пираты двигаются к своим целям по прямым со своей скоростью, им никто и ничто не мешает.

Вихідні дані

Для каждого теста вывести в отдельной строке одно действительное число: наименьшее время, через которое капитан убьет n-минога. Ответ следует вывести с точностью, не меньшей 10^{-6}.

Приклад

Вхідні дані #1
3
3 3
2 0 1
0 0 2
1 0 3
3 0 4
2 3
0 1
1 1
4 1
1 3
0 0 1
3 0 1
4 0 1
7 0 2
0 1
4 2
3 3
0 0 2
2 0 3
3 0 1
4 0 2
0 1
3 1
4 1
5 1
Вихідні дані #1
3.5
2.802775638
1.5
Джерело 2011 Benelux Algorithm Programming Contest, Preliminaries, Задача C