Point to Segment Distance
Very common problem in computational geometry is to find distance between the point and the line segment. It is
heavily exploited in programming 3D video games when recalculating visibility of walls for player while redrawing
each frame (i.e it is could be solved for
1000 wall fragments in each frame and about
50 frames are completely
recalculated during each second).
The definition of the distance between point and segment is like following:
For example, see the picture above - line segment is drawn with blue and perpendiculars from
fall directly onto this segment, so they represent the distance from these points. On other hand perpendiculars from
4th points fall out of segment (and they are not shown), so that distances are defined simply by the
nearest end of a segment (distances from all points are represented with grey lines). The line on which the segment
lays is shown with light-green.
Input data will contain the number of test-cases in first line.
The following lines contain six values each:
x1 y1 x2 y2 xp yp - denoting the segment between points
(x2,y2) and the point
(xp,yp) to which a distance should be calculated.
Answer should contain distances from points to segments for each test-case, separated with spaces.
input data: 3 1 1 5 5 2 3 2 3 7 8 2 0 12 8 18 3 5 7 answer: 0.707106781 3 7.07106781187
Note that in the second test-case the shortest distance from point is to the end of a segment, not to a line to which the segment belongs.
Please, provide answers with accuracy of
1e-7 or better.