P9030 [COCI 2022/2023 #1] Berilij

The little sheep Berilij was kidnapped by aliens. She needs to help the aliens solve a problem.

On the day of the COCI contest, the aliens plan to visit Earth with $n$ spaceships and give contestants generous rewards. Their spaceships are all perfect circles. For safety reasons, they chose $m$ pairs of spaceships that must be in external contact when landing. The aliens have already determined the landing point coordinates of each spaceship, and Berilij's task is to determine the radius of each spaceship so that all spaceships can land safely.  As shown in the figure, neither the left pair nor the right pair of spaceships satisfies the external contact condition. Only the middle pair satisfies the external contact condition. In other words, “external contact” is defined as: two spaceships are in external contact if and only if the corresponding circles are **externally tangent**. Spaceships are expensive to build, and their cost equals their area, so the aliens want the total cost to be as small as possible. Since the aliens are very advanced, their spaceships may overlap, and the diameter may also be $0$. If Berilij cannot solve this problem, the aliens will eat her. Please help the little sheep Berilij.

The first line contains two integers $n,m$, representing the number of alien spaceships and the number of pairs of spaceships that need to be in contact. The next $n$ lines each contain two real numbers $x_i,y_i$, representing the coordinates of the landing point of the $i$-th spaceship. The given coordinates are accurate to 10 digits after the decimal point. The following $m$ lines contain two integers $a_i$ and $b_i$, indicating that spaceship $a_i$ and spaceship $b_i$ must be in external contact after landing. The testdata guarantees that the unordered pairs $(a_i,b_i)$ are not repeated.

If there is no solution, output one line: ```NE``` Otherwise, output the first line: ```DA``` Then output $n$ lines, each containing the radius of a spaceship in a minimum-cost solution.

If the absolute or relative error of your answer is at most $10^{-4}$, it will be considered correct. | Subtask | Score | Special Property | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n$ is odd and every spaceship is in contact with exactly two spaceships | | $2$ | $25$ | The testdata guarantees a solution exists | | $3$ | $30$ | For any pair of spaceships $(a,b)$, there exists exactly one spaceship sequence that starts at $a$ and ends at $b$, and in this sequence every two adjacent spaceships are in contact with each other | | $4$ | $40$ | No special properties | Constraints: for $100\%$ of the testdata, $1\leq n,m \leq 10^5$, $-10^4\leq x_i,y_i \leq 10^4$, $1\leq a_i,b_i \leq n$, and $a_i \neq b_i$. The full score for this problem is 110 points. Translated by ChatGPT 5