
ZOJ Problem Set  3340
With the development of technology, we have the ability to travel through the space. Inspired by the curiosity of mankind, some people  such like us  tried to explore the outer solar system. We started our trip from the ZJU(Zero Joy Ultimate?) space station. Once the direction been selected, we have to adjust the spacecraft's course to guarantee us flying in a straight line. And to simplify this complex thing, we have decided to align our destination direction with the current(time of our spacecraft's launch) location of Neptune. Therefore, our flight path is a ray. But the problem is: we have to pass through the asteroid belt. The asteroids' effect of our spacecraft cannot be ignored. So we have to calculate each asteroid's distance from our flight path, to find the farthest one. This farthest distance allows us to understand the situation. Something you have to understand is that our spacecraft and the asteroids can be regarded as some points, which means that the "zero distance" is not your problem. For some details, see the sample input and output. Input There are several test cases. In each case, there will be one integer in the first line, N(1 <= N <= 100000), which represents the number of asteroids. The following two lines each contain three integers, which represent coordinates of the ZJU space station and coordinates of Neptune. The next N lines(thus the line 4 to N + 3) describe the asteroids, line i + 3(i from 1 to N) has three integers, which represent each asteroids' coordinates. We guarantee that every single value of coordinates in our problem is in range [1000000, 1000000]. Output For each test case, output the farthest distance between asteroid and our flight path, round to 0.01. Sample Input 6 0 0 0 1 0 0 0 1 1 5 1 0 5 0 1 5 0 1 5 1 0 5 0 0 1 5 5 5 6 6 6 100 0 0 Sample Output 1.41 81.65 Author: FAN, Yuzhe Source: ZOJ Monthly, May 2010 