P2588 [ZJOI2008] Risk

After several consecutive years of promotion, the game Risk has become popular nationwide and is now a widely enjoyed form of entertainment. Risk can be understood as a simple strategy game in which the player’s goal is to occupy all territories. According to the rules, any two countries that are adjacent are considered to have a possibility of engaging in war. We now want to determine, under the current situation, which pairs of countries may go to war. Note that we consider two countries adjacent only when their borders share a common edge; if two countries’ territories touch only at a single point, they are considered non-adjacent. The boundary of each country is composed of a sequence of line segments and is guaranteed to be a simple polygon, i.e., strictly non-self-intersecting. To locate each country, we also give the position of its largest army, which is guaranteed to lie strictly inside some region rather than on any boundary.

The first line contains two integers $n, m$, representing the number of countries on the map and the number of line segments that describe country borders, respectively. $1 \le n \le 600$, $1 \le m \le 4000$. The next $n$ lines each contain a pair of numbers giving the coordinates of a country’s main army. The next $m$ lines each contain four numbers $x_1, y_1, x_2, y_2$; the segment $(x_1, y_1)$–$(x_2, y_2)$ describes a border line. All point coordinates are integers between $0$ and $10000$ inclusive. It is guaranteed that the input line segments intersect at most at discrete intersection points. There is exactly one unbounded blank region on the entire map that does not belong to any country. For every border line, the regions on its two sides either belong to two different countries, or separate a country from that unbounded blank region. In other words, no border line has the same country on both sides, and no border line has blank regions on both sides. Every bounded region contains exactly one main army inside it, indicating that region’s owner.  For example, the first row in the figure above is valid. The data in the second row are all invalid: in the left image, both sides of a line segment are blank regions; in the middle image, both sides belong to the same country; in the right image, the army is placed on the border line, which is illegal; moreover, if the rightmost image had no army, that would also be illegal. The input is guaranteed to be valid; your program does not need to verify validity.

Output $n$ lines. In each line, the first number $x$ is the count of countries that may go to war with this country. Then, on the same line, output $x$ integers in ascending order, representing the indices of those countries. Countries are indexed $1$ to $n$ in the order they appear in the input. Separate numbers with exactly one space, and do not print extra spaces at the end of a line.

Translated by ChatGPT 5