Problem K
Zip Line Course
Input
The first line contains $s$, the number of supports $1 \le s \le 26$ and $l$, the number of proposed lines $1 \le l \le 20$ Supports are represented by consecutive upper-case letters starting with A (not appearing in the data). For each support there is a line giving its x, y coordinates in feet (we are only considering the first quadrant, so $0 \le x,y \le 10000$ for all x and y). Following the support details are lines detailing each proposed zip line. It begins with a two-letter support identifier followed by the heights of attachment at each support in feet above the ground respectively (so greater than 0, and less than or equal to 1000)
In the first sample input (sketch shown in the figure), there are 5 supports (labelled A-E) and 6 zip lines (labelled AB, AC, BE, BC, CE, and BD, according to the supports each spans.)
Output
Format as demonstrated as “XX XX too close” (X being a support letter) for each forbidden crossing and “n ziplines” for n being the maximum possible lines. List edges of the forbidden crossings in order of input. If two lines cross such that the vertical distance between them is less than $10^{-9}$ in absolute difference from 6, consider the crossing to be safe.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 6 170 240 260 150 170 40 60 80 40 210 AB 20 30 AC 20 40 BE 30 55 BC 20 40 CE 30 50 BD 20 45 |
AC BD too close CE BD too close 5 ziplines |
