P10343 [THUSC 2019] Tui En Order

In the early Western Han dynasty, Emperor Gaozu Liu Bang, in order to keep land more firmly in the hands of the Liu family, enfeoffed many princes with the surname Liu. However, after Liu Bang passed away, these princes became less and less controlled by the central government. To weaken the power of the vassal states, Emperor Wu of Han, Liu Che, adopted the suggestion of the court official Zhufu Yan and carried out the Tui En Order. The Tui En Order required each prince to split his land among all of his sons, instead of passing the title only to the eldest son. In this way, large kingdoms would be divided into several smaller vassal states, and the princes’ power would be reduced.

Consider a practical example. There is a prince, and his vassal state contains $n$ city-states, where city-state $s$ is the capital of his state. We describe his territory on a 2D Cartesian coordinate system. The $i$-th city-state can be regarded as a circle centered at $(x_i,y_i)$ with radius $r_i$. Any two city-states do not overlap (intersect), and they also do not touch each other (are not tangent). The prince has two sons, and he wants to divide his territory between them in a simple way: by building a boundary canal in his territory. This boundary canal can be represented by a straight line in the coordinate system. It must not pass through any city-state (intersect), and it must not pass through the boundary of any city-state (be tangent). This boundary canal divides the territory into two parts: the part containing the capital $s$ is given to the eldest son, and the other part is given to the younger son. To ensure that the younger son can also choose a city-state as his capital, each side of the boundary canal must contain at least one city-state. There can be many ways to build the canal. To ensure fairness, the prince wants to randomly choose one from all essentially different canal-building methods. If two canal-building methods split the city-states into the same two parts, then these two methods are considered essentially the same. The younger son has learned about the prince’s division method. To pick his capital in advance, he wants to know how likely each city-state is to become his capital. He gives this task to you. You need to compute: for each city-state, how many essentially different canal-building methods allow him to choose this city-state as his capital?

The first line contains two integers $n,s$, representing the number of city-states in the vassal state and the index of the capital. The next $n$ lines each contain three integers $x_i, y_i, r_i$. Line $i$ describes the center and radius of the $i$-th city-state.

Output $n$ lines. Each line contains one integer $a_i$. The $i$-th line means that there are $a_i$ essentially different canal-building plans that allow the younger son to choose the $i$-th city-state as his capital.

**[Sample 3]** See `3.in/ans` in the attached files. **[Subtasks]** For $100\%$ of the testdata, $1\leq s\leq n\leq 1000$, $0\leq |x_i|, |y_i|, r_i \leq 10^4$. | Subtask ID | Points | Special Constraints | | :--: | :--: | :--: | | 1 | 17 | $n\leq 18$ | | 2 | 29 | $n\leq 100$ | | 3 | 22 | $r_i=0$ | | 4 | 32 | None | Translated by ChatGPT 5