PEG Judge - Math on Titan

Don Mills Open Programming Competition -- November 2013

Math on Titan

The titans (giants) are coming! To make time for the civilians to escape, Mikasa will launch an attack on the giants. To destroy a giant, Mikasa must slash precisely at the back of their neck with her blade. The necks of the giants may vary in height, because not all giants are made equal. Conveniently, all giants are perfectly upright and lined up in a row today, so it is possible to represent their necks as vertical line segments defined by two points. Mikasa's attack can be also be defined by two points, and consists of the line segment formed by those two points. A giant is considered to be destroyed if the line defined by the starting and ending coordinates of Mikasa's attack intersects the line segment which represents the giant's neck (including passing through endpoints). Mikasa is running low on the fuel source which enables her to fly (to reach the taller giants), so she can only launch one attack. Your task is calculate her optimal flight path, which must adhere to the following restrictions:

Mikasa begins her attack at the point (0, a), where a is a non-negative real number.
Mikasa ends her attack at the point (100, b), where b is also a non-negative real number.
No other possible flight path will destroy more giants than the one Mikasa will take.
Out of all the possible flight paths that destroy the same number of giants (and this number is maximal), the path Mikasa will take has the starting coordinate with the lowest a value. If multiple flight paths share the lowest a value, then Mikasa's path will have the lowest b value.

Input Format

The first line of input will contain an integer G (1 ≤ G ≤ 50), the number of giants close to the town.
The next G lines will each contain a description of a giant's neck. The first number of each line will be the x-coordinate of the giant's neck, and the remaining two numbers will be the y-coordinates of the bottom and top of the giant's neck, respectively. You may assume that the bottom y-coordinate will be strictly less than the top y-coordinate. Each of these three coordinates will be an integer between 1 and 100, inclusive.

Output Format

The first line of output must contain the number of giants Mikasa destroys on her optimal flight path.
The second line of output must contain the y-coordinate of her starting point, a.
The third line of output must contain the y-coordinate of her ending point, b.
Both y-coordinates should be accurate to at least 5 decimal places.

Sample Input 1

Sample Output 1

3
1
101

Explanation for Sample 1

Mikasa can go along the line y = x + 1 to destroy the first three giants. No more than three giants can be destroyed on any valid flight path. Since there are multiple ways to destroy the first three giants, she chooses the best way as described in the problem statement.