Problem E
Fragile Diamonds
Languages
en
pt
John the jeweler is an ambitious merchant that sells diamonds to several types of clients that require diamonds of different sizes. Even though his business network is quite vast, he is not the most careful salesman and often, when storing new diamonds in stock, he ends up breaking diamonds that were there previously.
John’s stock is so enormous that it can be abstracted by the infinite half-plane of $y \geq 0$ where the diamonds are placed on the floor ($x$-axis). Each diamond can be represented as a square rotated at $45$ degrees relative to the coordinate axes. Diamonds touch the ground ($x$-axis) with one vertex and all its other points have positive $y$ coordinates.
John receives $n$ diamonds, which are put into stock one after another and are numbered from $1$ to $n$ in order of the input. The $i$-th diamond is defined by $x_ i$ and $y_ i$, the coordinates of its center.
For each diamond stored you should say how many and which diamonds previously found in the stock the last diamond breaks, i.e. which diamonds that have not been broken yet and whose intersection with the newly placed diamond has non-zero area (note that when a diamond is placed in the stock it does not break even if it breaks other diamonds, and the diamonds that are broken should not be considered by the following diamonds).
Input
The first line of the input contains an integer $n$ ($2 \leq n \leq 100\, 000$), the number of diamonds stored by John. Then following $n$ lines, numbered from $1$ to $n$ in order that are given, contain two integers each, $x_ i$ and $y_ i$ ($-1\, 000\, 000\, 000 \leq x_ i \leq 1\, 000\, 000\, 000, 1 \leq y_ i \leq 1\, 000\, 000\, 000$) the center of the diamond $i$.
Output
Print $n$ lines, each described by an integer $q_ i$, the quantity of diamonds broken on the $i$-th insertion, followed by $q_ i$ integers, the indexes in ascending order of all the previously stored diamonds that are broken by storing the $i$-th diamond. Indexes of the diamonds numbered from $1$ to $n$ in order that are given in the input.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 -1 1 1 1 1 2 0 1 |
0 0 1 2 2 1 3 |
