Colorful_Diameter (OOI qualification)
Time limit: 7 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: optimization, geometry, convex hull, ternary search

# Colorful Diameter

| Input file:   | `standard input`  |
|---------------|-----------------|
| Output file:  | `standard output` |
| Time limit:   | 7 seconds       |
| Memory limit: | 512 megabytes   |

On a plane, there are $n$ points with coordinates $(x_i, y_i)$; each point has a color $c_i$. Each point moves at a constant speed along the vector $(dx_i, dy_i)$ per second. This means that every second, the value $dx_i$ is added to the x-coordinate of point $i$, and the value $dy_i$ is added to the y-coordinate of the point.

For all integer moments in time during the first $T$ seconds, find the minimum of the maximum distance between points of different colors. In other words, find such an integer moment in time $t$ ($0 \le t \le T$) that the maximum distance between points of different colors at that moment is minimized compared to any other integer time from 0 to $T$.

## Input

Each test consists of several sets of input data. The first line contains one integer $t$ ($1 \le t \le 100\,000$) — the number of input data sets. The description of the input data sets follows.

The first line of each input data set contains two integers $n$ and $T$ ($2 \le n \le 200\,000$, $0 \le T \le 10^8$) — the number of points and the time interval considered.

Each of the following $n$ lines describes the points. The $i$-th line contains five integers $x_i$, $y_i$, $dx_i$, $dy_i$, and $c_i$ ($-10^8 \le x_i, y_i, dx_i, dy_i \le 10^8$, $1 \le c_i \le n$) — the coordinates, speed in each coordinate, and the color of point $i$.

It is guaranteed that there are two points with different colors.

It is guaranteed that the sum of $n$ across all input data sets in each test does not exceed $200\,000$, and the sum of $T$ does not exceed $10^8$.

It is guaranteed that any coordinates of the points at any moment in time up to $T$ inclusive do not exceed $10^9$ in absolute value.

## Output

For each input data set, output one number on a separate line — the minimum of the maximum distance between points of different colors during the first $T$ seconds.

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

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^{-9}$.

## Example

| standard input | standard output |
|----------------|-----------------|
| 3              | 2.8284271247    |
| 3 0            | 0.0000000000    |
| 1 1 0 0 1      | 2.8284271247    |
| 2 2 0 0 2      |                 |
| 4 4 0 0 1      |                 |
| 2 2            |                 |
| 0 0 1 1 1      |                 |
| 2 2 -1 -1 2    |                 |
| 4 100          |                 |
| 0 0 0 1 1      |                 |
| 4 0 -1 0 2     |                 |
| 4 4 0 -1 1     |                 |
| 0 4 1 0 2      |                 |

## Note

Consider the example from the statement.

In the first input data set, only one moment in time is considered. The distance between the first and second points is $\sqrt{2}$, and between the second and third points is $2\sqrt{2}$. Therefore, the answer is $2\sqrt{2}$.

In the second input data set, at time 1, the points will coincide, and the distance between them will be zero. Therefore, the answer is 0.

In the third input data set, it can be shown that the minimum maximum distance between points of different colors is achieved at time 2 and equals $2\sqrt{2}$.

The figure shows the third input data set for moments in time $t = 0, 1, 2$. Points of color 1 are marked in red, and points of color 2 are marked in blue.

![](_page_1_Figure_8.jpeg)

## Scoring

The tests for this problem consist of nine groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

Let $\sum n$ be the sum of $n$ across all input data sets of this test.

Let $\sum T$ be the sum of $T$ across all input data sets of this test.

| Group | Points | Additional constraints |   | Required groups | Comment                               |
|-------|--------|------------------------|---|-----------------|---------------------------------------|
|       |        | $\sum n$               | $\sum T$  |                 |                                       |
| 0     | 0      | -                      | - | -               | Samples.                              |
| 1     | 10     | $\sum n \le 100$       | $\sum T \le 10$ | 0               |                                       |
| 2     | 8      | $\sum n \le 10\,000$    | $\sum T \le 10$ | 0, 1            |                                       |
| 3     | 11     | $\sum n \le 100$       | - | 0, 1            |                                       |
| 4     | 14     | $\sum n \le 100\,000$   | $\sum T \le 10$ | -               | Three are exactly 2 different colors. |
| 5     | 8      | $\sum n \le 100\,000$   | - | 4               | There are exactly 2 different colors. |
| 6     | 11     | $\sum n \le 100\,000$   | $\sum T \le 10$ | -               | All colors are different.             |
| 7     | 8      | $\sum n \le 100\,000$   | - | 6               | All colors are different.             |
| 8     | 19     | $\sum n \le 100\,000$   | - | 0 – 7           |                                       |
| 9     | 11     | -                      | - | 0 – 8           | Offline-testing.                      |

Starter code:

Grader code:

Setup script:

Evaluation script: