TLE '17 Contest 2 P3 - Willson and MigrationView as PDF
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 families of migrating geese, numbered from to . Willson's family is family . The family's journey can be represented by a ray starting at point and heading toward the point . 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 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 units of his family during the flight.
for all .
for all .
For of the points, for all .
For an additional of the points, either or for all .
The first line of input will contain two integers: , the number of families of geese, and .
lines of input follow. The line will contain five integers: .
Output, on separate lines and in order, the families that come within units of Willson's family. If there are no such families, do not output anything.
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
Report an issue