Falling cards#2650
It is hard to make a playing card stand on its edge, but a patient person has managed to place cards on the table so that each card stands on its shorter edge. The view from above of the table with cards can be represented by a set of line segments with coordinates (x_i, y_i) to (v_i, w_i). The segments do not intersect.
The first card falls flat onto its side, causing any card it touches to fall as well. The angle between the vector (x_1, y_1)–(v_1, w_1) and the falling direction of the first card is degrees (measured counter-clockwise). If card touches card , the direction of ’s fall is chosen so that the continuation of the direction vector does not cross the line containing segment . The input data is guaranteed to never contain:
1. a card falling exactly perpendicular to another card; 2. a falling card that touches more than one of the still standing cards.
Your program must determine which cards will fall and which will remain standing.
The first line of the input file contains the numbers (1 \leq N \leq 100, H > 0) — the number of cards and the floating-point height of a card. Each of the next lines contains four floating-point numbers x_i y_i v_i w_i — the coordinates of the cards, separated by spaces.
The output file must contain the list of fallen cards’ numbers, sorted in increasing order and separated by spaces.
Example 1