题目描述

Emma, a young astronomer, has just received an award from the International Cosmic and Planetary Committee (the ICPC) for her discovery of a new planetary system along with her novel method in recording the planetary system.

The new planetary system consists of a single star with $N$ planets orbiting it. All these planets are orbiting on the same plane such that they can be drawn easily on a 2-dimensional surface. Moreover, each of these planets has a perfectly circular orbit centered at the star. All planets revolve around the star in the same counter-clockwise direction.

To simplify this problem, the star and each planet are represented by a point and their sizes are negligible. The star is located at the origin.

Through her research, Emma managed to record the location of each planet along with their revolution period (the time needed for a planet to complete one full orbit around the star). Specifically, Emma records $\langle R_{i}, \theta_{i}, T_{i}\rangle$ for each planet where $\langle R_{i}, \theta_{i}\rangle$ is its polar coordinate and $T_{i}$ is its revolution period. A polar coordinate $\langle R_{i}, \theta_{i}\rangle$ means that its distance to the star is $R_{i}$ and its angle from the polar axis (positive x-axis) is $\theta_{i}$. To have an integer input, the degree $\theta_{i}$ is multiplied by 1000, so the value is between 0 and 359 999 (inclusive) representing any degree between $0^{\circ}$ and $359.999^{\circ}$.

Emma records all these planets' positions at the same time, i.e. at time $t = 0$. Observe that the position of each planet may differ on $t > 0$ depends on their revolution period, e.g., a planet at $\langle 3, 180 000 \rangle$ at $t = 0$ with a revolution period of 4 unit will be at $\langle 3, 270 000 \rangle$ when $t = 1$ and at $\langle 3, 315 000 \rangle$ when $t = 1.5$; at $t = 4$ (its revolution period), this planet will complete its orbit and return to $\langle 3, 180 000 \rangle$.

Emma hypothesizes that a planetary system will be much more stable if the planets are not too close to each other. As no analysis has been done on this new planetary system, Emma wants to know the minimum distance among all pairs of planets in this new planetary system. To measure the distance, Emma simply uses the Euclidean distance on a 2-dimensional plane.

The distance between two planets is defined as the closest distance that these two planets can ever achieve, i.e. for any $t \in [0, \infty)$. Note that $t$ can be a real number. For example, let there be two planets $\langle 3, 180 000, 4 \rangle$ and $\langle 4, 0, 2 \rangle$. The distance between these two planets at $t = 0$ is 7 unit; their positions are the opposite to each other from the star, i.e. the first planet is at $180^{\circ}$ while the second planet is at $0^{\circ}$. When $t = 2$, the first planet will travel half of its orbit and its position becomes $\langle 3, 0 \rangle$, at the opposite side from its position when $t = 0$. On the other hand, the second planet will travel one complete orbit so that its position is the same as in when $t = 0$, i.e. $\langle 4, 0 \rangle$. In this situation, their distance is 1 unit. This is the closest distance these two planets will ever achieve, thus, the distance between these two planets is 1 unit.

Given the position at time $t = 0$ and the revolution period of each planet, your task is to determine the minimum distance among all pairs of planets. If there exist two planets colliding (being at the same position) for any $t > 0$, then simply output 0; such a planetary system is not stable.

输入格式

Input begins with an integer $N$ ($2 \leq N \leq 200 000$) representing the number of planets in the new planetary system. The next $N$ lines, each contains three integers $R_{i}$ $\theta_{i}$ $T_{i}$ ($1 \leq R_{i}, T_{i} \leq 10^{8}$; $0 \leq \theta_{i} < 360 000$) representing the $i^{th}$ planet's position in a polar coordinate $\langle R_{i}, \theta_{i}\rangle$ at $t = 0$, and its revolution period, respectively. The polar coordinate $\langle R_{i}, \theta_{i}\rangle$ means that the planet's distance to the star is $R_{i}$ and its angle from the polar axis is $\theta_{i}$. It is guaranteed that there are no two planets with the same position at $t = 0$.

输出格式

Output contains a single real number representing the minimum distance among all pairs of planets as defined in the problem description. If there exist two planets colliding at a certain time, then output 0. Your answer will be accepted as long as its absolute or relative error does not exceed $10^{-6}$.

3
1 55555 4
3 180000 4
4 0 2

1

3
100 0 2
100 270000 1
9 2000 3

0

2
10 0 2
1 90000 2

10.0498756211

提示

Explanation for the sample input/output #1

At $t = 0$, the planets' positions are shown as in the following figure.

:::align{center} :::

The minimum distance can be obtained from the pair of the $2^{nd}$ and $3^{rd}$ planet at time $t = 2$. The following figure shows the planets' positions at $t = 2$.

:::align{center} :::

Explanation for the sample input/output #2

The $1^{st}$ and $2^{nd}$ planet will collide at $t = 0.5$, i.e. when both are at $\langle 100, 90000 \rangle$.

Explanation for the sample input/output #3

The distance between the $1^{st}$ and $2^{nd}$ planet will always be the same all the time.