Under construction

Still being built. Things may change

Pick-up Sticks

Time limit1sMemory limit128 MB

Summary
Given line segments thrown in order, report the segments not crossed by any later segment, using segment intersection tests.
Level

Medium7 of 10

Topics
Geometry, Brute force, Sorting, Implementation
Solved
No attempts yet

Problem

Stan has nn sticks of various lengths. He throws them onto the floor one at a time, in a random way. The sticks are so thin that their thickness can be ignored.

After he finishes throwing, Stan wants to find the top sticks — the sticks that have no other stick lying on top of them. A stick BB lies on top of a stick AA if BB was thrown after AA and the two sticks cross each other (touching at an endpoint counts as crossing). A stick is a top stick if none of the sticks thrown after it crosses it.

The last stick thrown is always on top. Find every stick that is on top.

Input

The input consists of several test cases. The first line of each case contains the number of sticks nn (1≤n≤100000)(1 \le n \le 100000). Each of the next nn lines contains four real numbers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2, the planar coordinates of the two endpoints of one stick. The sticks are listed in the order in which Stan threw them. You may assume that there are no more than 10001000 top sticks.

The input ends with a case where n=0n = 0; this case must not be processed.

Output

For each test case, print the top sticks on one line, in the order in which they were thrown, using the format:

Top sticks: a, b, c.

That is, print Top sticks: followed by the indices of the top sticks in throwing order, separated by , (a comma and a space), and end the line with a period .. The sticks are numbered 1,2,…,n1, 2, \dots, n in the order given in the input.

Examples1

  1. Example 1

    Input
    5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0
    Expected output
    Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.