Məsələlər
Falling cards
Falling cards
It is hard to make the playing card stand on its edge, however, some patient person managed to put \textbf{N} of them upon the desk in such a way that each cards stands on its shorter edge. The top-down view of that desk with cards upon it can be represented with the set of line segments with coordinates (\textbf{x_i}, \textbf{y_i}) to (\textbf{v_i}, \textbf{w_i}). The segments do not intersect.
The first card falls flat on its side, causing any card it touches to fall down also. The angle between vector (\textbf{x_1}, \textbf{y_1})--(\textbf{v_1}, \textbf{w_1}) and the falling direction of the first card is equal to \textbf{90} degrees (measured counter-clockwise). If card \textbf{A} touches card \textbf{B}, the direction of \textbf{B}’s fall is chosen so that the continuation of the direction vector does not cross the line containing segment \textbf{A}. Input data are guaranteed to never contain:
\begin{enumerate}
\item a card falling exactly perpendicular to the other and
\item a falling card that touches more than one of still standing cards.
\end{enumerate}
Your program must determine which cards will fall, and which shall remain standing.
\InputFile
The first line of input file contains a numbers \textbf{N} \textbf{H} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}, \textbf{H} > \textbf{0}) --- the number of cards and the floating point height of a card. Each of the following \textbf{N} lines contains four floating-point numbers \textbf{x_i y_i v_i w_i} --- coordinates of cards separated by spaces.
\OutputFile
The output file must contain the list of fallen cards’ numbers, sorted in increasing order and separated by spaces.
Giriş verilənləri #1
3 100 10 10 50 40 10 0 50 30 20 90 20 20
Çıxış verilənləri #1
1 3