시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.3 초 | 1024 MB | 9 | 5 | 5 | 55.556% |
It is Hubert’s first slalom race, so naturally he feels very nervous. Moreover, it is also his first day on skis and he has not learnt how to make turns yet – he can only slide along a straight line. But nothing is lost yet. Maybe the designer of this particular course was not careful enough, so it is actually possible to pass through every gate without taking a single turn.
You are given the description of a slalom course with n gates. The course runs from left to right. Each gate is represented by a vertical line segment between two poles. From a bird’s-eye view, Hubert looks like a disk with diameter d (d ≥ 0) and the trajectory of his center follows a straight line. He can choose his start point anywhere to the left of the leftmost gate, and his finish point anywhere to the right of the rightmost gate. To complete the course, Hubert must pass with his entire body between the poles of all gates. Touching the poles is allowed.
Find the largest diameter d such that there is a trajectory enabling Hubert to complete the course.
The first line of the input contains a single integer n – the number of gates (1 ≤ n ≤ 105). Each of the n following lines describes a gate and consists of three space-separated integers x, y1, y2 (0 ≤ x ≤ 109 , 0 ≤ y1 ≤ y2 ≤ 109). The described gate is the vertical line segment with endpoints [x, y1] and [x, y2]. No two gates have the same x-coordinate.
Output a single line with the largest d such that Hubert can complete the course. We will accept answers with absolute or relative error less than 10−9 . In C++, you can output the answer using printf("%.10lf\n", d);
If there is no such non-negative value of d, output a single line with word Impossible.
3 4 3 7 6 6 9 1 5 10
1.3728129460
2 3 7 9 10 4 4
0.0000000000
3 0 4 7 2 0 3 4 4 7
Impossible