5434번 - Attack of the Giant n-pus 스페셜 저지다국어

A pirate ship is being attacked by a giant n-pus¹. The n tentacles and the head of the creature have pierced the deck and are wreaking havoc on the ship. In an attempt to stop the creature from completely destroying the ship, the captain charges towards the head of the creature. Unfortunately, he quickly gets knocked back by one of the tentacles. The captain realizes he cannot attack the head of the n-pus as long as it can move its tentacles freely.

Luckily the captain is not alone on the ship. There are p (p ≥ n) pirates spread around on the deck, ready to follow the captain’s orders. So the captain comes up with the following plan. If each tentacle is attacked by one of the pirates, he can move freely towards the head of the creature and finish it off. To be safe, the captain will start moving only after each of the tentacles is being attacked by a pirate. When the captain reaches the head, he can instantly kill the creature. The captain wants to figure out which pirates to send to which tentacles, such that the creature can be killed as fast as possible. As this happens regularly to pirates, the captain wants you to write a program to solve this problem.

¹An n-pus is like an octopus, but then with n tentacles.

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with two integers n and p, satisfying 1 ≤ n ≤ p ≤ 100: the number of tentacles of the n-pus and the number of pirates (excluding the captain), respectively.
• One line with three integers x_c, y_c and v_c: the captain’s coordinates and speed, respectively.
• p lines, each with three integers x_i, y_i and v_i: the coordinates and speed, respectively, of each pirate.
• One line with two integers x_h and y_h: the coordinates of the head of the n-pus.
• n lines, each with two integers x_j and y_j : the coordinates of each tentacle.

All coordinates satisfy 0 ≤ x, y ≤ 10, 000. All speeds satisfy 1 ≤ v ≤ 100.

The captain, the pirates, the head and the tentacles are all considered to be point-like (i.e. they have no size). Their locations are all distinct.

The captain and all pirates move to their target in a straight line at their given speed and are not hindered by anyone or anything.

For every test case in the input, the output should contain one floating point number on a single line: the minimum time it takes for the captain to kill the n-pus. Your answer should have either an absolute or a relative error of at most 10^-6.