RC Kaboom Show
Contest: Educational Codeforces Round 88 (Rated for Div. 2)
Difficulty rating: 2900
Tags: binary search, brute force, data structures, geometry, math

You know, it's hard to conduct a show with lots of participants and spectators at the same place nowadays. Still, you are not giving up on your dream to make a car crash showcase! You decided to replace the real cars with remote controlled ones, call the event "Remote Control Kaboom Show" and stream everything online.

For the preparation you arranged an arena — an infinite 2D-field. You also bought $$$n$$$ remote controlled cars and set them up on the arena. Unfortunately, the cars you bought can only go forward without turning left, right or around. So you additionally put the cars in the direction you want them to go.

To be formal, for each car $$$i$$$ ($$$1 \le i \le n$$$) you chose its initial position ($$$x_i, y_i$$$) and a direction vector ($$$dx_i, dy_i$$$). Moreover, each car has a constant speed $$$s_i$$$ units per second. So after car $$$i$$$ is launched, it stars moving from ($$$x_i, y_i$$$) in the direction ($$$dx_i, dy_i$$$) with constant speed $$$s_i$$$.

The goal of the show is to create a car collision as fast as possible! You noted that launching every car at the beginning of the show often fails to produce any collisions at all. Thus, you plan to launch the $$$i$$$-th car at some moment $$$t_i$$$. You haven't chosen $$$t_i$$$, that's yet to be decided. Note that it's not necessary for $$$t_i$$$ to be integer and $$$t_i$$$ is allowed to be equal to $$$t_j$$$ for any $$$i, j$$$.

The show starts at time $$$0$$$. The show ends when two cars $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) collide (i. e. come to the same coordinate at the same time). The duration of the show is the time between the start and the end.

What's the fastest crash you can arrange by choosing all $$$t_i$$$? If it's possible to arrange a crash then print the shortest possible duration of the show. Otherwise, report that it's impossible.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 25000$$$) — the number of cars.

Each of the next $$$n$$$ lines contains five integers $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, $$$dy_i$$$, $$$s_i$$$ ($$$-10^3 \le x_i, y_i \le 10^3$$$; $$$1 \le |dx_i| \le 10^3$$$; $$$1 \le |dy_i| \le 10^3$$$; $$$1 \le s_i \le 10^3$$$) — the initial position of the $$$i$$$-th car, its direction vector and its speed, respectively.

It's guaranteed that all cars start at distinct positions (i. e. $$$(x_i, y_i) \neq (x_j, y_j)$$$ for $$$i \neq j$$$).

Output format:
Print the shortest possible duration of the show if it's possible to arrange a crash by choosing all $$$t_i$$$. Otherwise, print "No show :(".

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
Here is the picture for the first example:

The fastest cars to crash are cars $$$2$$$ and $$$4$$$. Let's launch car $$$2$$$ at $$$0$$$, car $$$4$$$ at about $$$0.096762$$$ and cars $$$1$$$ and $$$3$$$ at arbitrary time. That way cars $$$2$$$ and $$$4$$$ will crash into each other at about $$$0.585902$$$. So here's what it looks like at the moment of the collision:

Here's the picture for the second example:

Example input:
4
3 -1 -1 1 2
2 3 -3 -2 10
-4 2 1 -2 1
-2 -2 -1 2 4

Example output:
0.585902082262898

Example input:
2
-1 1 -1 1 200
1 1 1 5 200

Example output:
No show :(

Editorial:
Let $$$f(t)$$$ be true if it's possible to have a collision before time $$$t$$$. That function is monotonous, thus let's binary search for $$$t$$$.
For some fixed $$$t$$$ car $$$i$$$ can end up in any point from $$$(x_i, y_i)$$$ to $$$s_i \cdot t$$$ units along the ray $$$((x_i, y_i), (x_i + dx_i, y_i + dy_i))$$$. That makes it a segment.
So the collision can happen if some pair of segments intersects. Let's learn how to find that out.
The general idea is to use sweep line. So let's add the events that the $$$i$$$-th segment $$$(x1_i, y1_i, x2_i, y2_i)$$$ such that $$$x1_i < x2_i$$$ opens at $$$x1_i$$$ and closes at $$$x2_i$$$. There were no vertical segments, so $$$x1_i$$$ and $$$x2_i$$$ are always different.
At every moment of time $$$T$$$ we want to maintain the segments ordered by their intersection with the line $$$x = T$$$. Note that if two segments change their order moving along the sweep line, then they intersect.
So we can maintain a set with a custom comparator that returns if one segment intersects the current line lower than the other one.
When adding a segment to set, you want to check it's intersections with the next segment in the order and the previous one. When removing a segment, you want to check the intersection between the next and the previous segment in the order. If any check triggers, then return true immediately. It's easy to show that if the intersection happens between some pair of segments, then the intersection between only these pairs of segment also happens.
Now for the implementation details. Precision errors play a huge role here since we use binary search and also store some stuff dependant on floats in the set.
The solution I want to tell requires no epsilon comparisons, thus it calculates the answer only with the precision of binary search.
So the first issue rises when we have to erase elements from the set. Notice that we can make a mistake when we are adding the segment and there is a segment with almost the same intersection point. That will not make the answer incorrect (that's not trivial to show but it's possible if you consider some cases). If you can find it later to remove, then it's not an issue at all. However, that will probably mess up the lower_bound in the set.
Thus, let's save the pointer to each element in the set and remove it later by that pointer.
The second issue comes when you have to check the intersection of two segments. The error might appear when one segment $$$((x_i, y_i), (nx_i, ny_i))$$$ (let the first point be the original $$$(x_i, y_i)$$$ and the second point be calculated depending on $$$t$$$) has it's intersection point with segment $$$((x_j, y_j), (nx_j, ny_j))$$$ at exactly $$$(x_i, y_i)$$$. So the slightest miscalculations could matter a lot.
Let's learn to intersect in such a way that no epsilon comparisons are required. Firstly, we can store lines in the set instead of segments. Second, we can check the intersection of rays first and only then proceed to check the intersection of segments.
So two rays intersect if:
• their lines intersect — easy to check in integers;
• the intersection point lies in the correct direction of both rays — the intersection point is always a pair of fractions $$$(\frac{Dx}{D}, \frac{Dy}{D})$$$ and you want to compare the signs of $$$dx_i$$$ and $$$\frac{Dx}{D} - x_i$$$.
Finally, if all the checks hold, then you can compare maximum of distances from $$$(x_i, y_i)$$$ and $$$(x_j, y_j)$$$ to the intersection point and $$$t$$$. If $$$t$$$ is greater or equal then they intersect in time. There is no way to make that comparison in integers. However, it's precision only depends on the precision of $$$t$$$ as in the error here can't affect the answer greatly.
Overall complexity: $$$O(n \log n \log maxt)$$$.