Planet Destruction

Darth Vader is back to his favourite hobby: destroying planets (or their population to be precise). He just discovered that the rebel leadership has gathered at a planet named Watooine, so he must act quickly to eliminate the threat. Unfortunately, the Empire is in a pretty bad recession right now, so there aren’t any Death Stars left around. Therefore, Vader’s plan involves dropping several containers with deadly viruses onto the planet’s surface.

To make things simpler for you, we will model this problem in 2D. Watooine has radius $R$ and is centred at $(0,0)$. There are $K$ Empire spaceships, each of which will simultaneously launch a rocket with a container towards point $(0, 0)$. Once the rocket hits the surface of the planet, a virus will start spreading along the surface in the shape of a circle of ever increasing radius. Since we are modelling the problem in 2D, the virus spreads from the point of impact at the same rate in both directions, clockwise and counterclockwise along the circumference of the circle that represents the surface of the planet. Each spaceship has a custom rocket speed, and each virus has a custom spread speed. Note that each virus spreads along the surface of the planet—it cannot pass through the planet to reach the other end.

Your task is to determine how much time will it take for Watooine to become completely infected—i.e., every point on the planet surface has been reached by a virus. Good luck!

\includegraphics[width=0.8\textwidth ]{E.png}
Figure 1: Sample input


The first line contains $T$, the number of test cases, followed by the descriptions of the $T$ test cases. Each test case description has the following structure: The first line contains two integers $R$, the radius of the planet (in meters), and $K$, the number of spaceships. The next $K$ lines each contain $4$ integers: the $X$-coordinate of the ship, the $Y$-coordinate of the ship, the rocket speed and the virus spread speed (in meters per second). It is guaranteed that no ships are inside the planet.

Both speeds are between $1$ and $1\, 000\, 000$, both coordinates are between $-1\, 000\, 000$ and $1\, 000\, 000$, $R$ is between $1$ and $1\, 000\, 000$. $K$ is between $1$ and $10\, 000$, and $T$ is between $1$ and $10$.


For each test case, print one line containing one real number, the time it takes for the planet to become completely infected. Your answer will be considered correct if it is within $10^{-4}$ from the jury answer.

Sample Input 1 Sample Output 1
100 1
200 0 10 7
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.6hard
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in