Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Falling cards
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 296Accepted: 70

Description

It is hard to make the playing card stand on its edge, however, some patient person managed to put 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 (xi, yi) to (vi, wi). The segments do not intersect.

The first card falls flat on its side, causing all the cards in touch to fall down also. The angle between vector (x1, y1)-(v1, w1) and the falling direction of the first card is equal to 90 degrees (measured counter-clockwise). If card A touches card B, the direction of B's fall is chosen so that the continuation of the direction vector does not cross the line containing segment A. Input data are guaranteed to never contain:
  • a card falling exactly perpendicular to the other and
  • a falling card that touches more than one of still standing cards.

Your program must determine which cards will fall, and which shall remain standing.

Input

The first line of input file contains a numbers N H - the number of cards and the floating point height of a card. Each of the following N lines contains four floating-point numbers xi yi vi wi - coordinates of cards separated by spaces. 1 <= N <= 100, H > 0

Output

The output file must contain the list of fallen cards' numbers, sorted in increasing order and separated by spaces.

Sample Input

3 100
10 10 50 40
10 0 50 30
20 90 20 20

Sample Output

1 3

Source

Northeastern Europe 2002, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator