TLE '17 Contest 2 P3 - Willson and Migration

View as PDF

Submit solution

Points:10 (partial)
Time limit:2.0s
Memory limit:256M

Problem type

Willson and his family migrating.

Willson the Canada Goose is like any other Canada goose - he migrates south for winter. As anyone knows, geese like to travel with their families.

Today, Willson is migrating with his family. There happen to be N families of migrating geese, numbered from 1 to N. Willson's family is family 1. The i^{th} family's journey can be represented by a ray starting at point (x_{i1},y_{i1}) and heading toward the point (x_{i2},y_{i2}). Note that families do not stop upon reaching their heading point. It is guaranteed that the starting and heading points are distinct. Each family begins flight at the same time and flies at a speed of v_i units per second, indefinitely.

However, when families collide, some geese might accidentally follow the wrong family. Willson wants to ensure that his family will remain together. Please tell him which other families of geese might come within R units of his family during the flight.


1 \le N \le 10^4

1 \le R \le 10^4

-10^4 \le x_{i1},y_{i1},x_{i2},y_{i2} \le 10^4 for all i.

1 \le v_i \le 10^4 for all i.

For 30\% of the points, y_{i1} = y_{i2} for all i.

For an additional 30\% of the points, either y_{i1} = y_{i2} or x_{i1} = x_{i2} for all i.

Input Specification

The first line of input will contain two integers: N, the number of families of geese, and R.

N lines of input follow. The i^{th} line will contain five integers: x_{i1}, y_{i1}, x_{i2}, y_{i2}, v_i.

Output Specification

Output, on separate lines and in order, the families that come within R units of Willson's family. If there are no such families, do not output anything.

Sample Input

5 5
0 0 1 1 10
-4 -5 0 -1 9
10 4 9 4 2
100 200 101 100 7
2 6 0 6 24

Sample Output


Report an issue


  • 1
     commented on Nov. 1, 2017

    Precision Error plox