JDCC '17 Contest 2 S3 - Santa's Flight

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

In order for Santa to deliver presents to all the kids in the world in one night, his sleigh needs to travel at nearly the speed of light. This has two main consequences: his sleigh can only travel in straight lines and it presents a hazard to any object in its way.

Santa’s main worry is hitting passenger planes, so he has decided to look up the N flights that are happening on Christmas Eve. Each flight path can be modelled using a linear equation y = mx + b.

Given the flights happening that night and some of the trips that Santa has to make, can you help Santa figure out during which of his flights he should be mindful of planes?


The first line of input contains an integer N\ (1 \le N \le 10).

N lines follow, each containing two integers M, B between -1\ 000 and 1\ 000 inclusive which describe one of the flights. It is guaranteed that the start and end point locations are not the same.

The next line of input contains an integer T\ (1 \le T \le 100), the number of trips Santa wants you to check.

T lines follow, each containing four integers X_1, Y_1, X_2, Y_2 between 0 and 1000 inclusive, which describe one of Santa’s desired trips.


For each trip Santa wants you to check, output Coast Clear if his path does not intersect any passenger flights, or Danger Ahead if his path will cross the flight path of a passenger plane.

Sample Input

0 0
1 0
0 0 1 4
1 2 3 2
3 2 3 3
1 2 1 3

Sample Output

Danger Ahead
Danger Ahead
Danger Ahead
Coast Clear


There are no comments at the moment.