Path by a Castle
Jared and Payton are on the 2D plane, at locations (xa, ya) and (xb, yb), respectively. They want to meet, but Payton is lazy and doesn't want to move. So Jared wants to walk to Payton's location. But Jared is also lazy, so he wants to do it with the shortest distance possible.
Unfortunately, a castle stands in their way. The castle is an enclosure of walls whose shape is the quadrilateral with vertices (x1, y1), (x2, y2), (x3, y3) and (x4, y4), in that order. The walls themselves are infinitely thin, but Jared is not allowed to cross it, or even get near them by a distance of 10-100.
What is the shortest distance that Jared can take to get to Payton's location?
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains four integers, xa, ya, xb, and yb, separated by single spaces.
The ith line in the next four lines contains two integers, xi and yi, separated by a space.
For each test case, output a single line containing a single real number: the answer to the problem. If there is no path at all, print -1. Your answer will be considered correct if it is within a relative error of 10-6 from the correct answer.
- 1 ≤ T ≤ 105
- The absolute values of the coordinates are at most 105.
- Jared and Payton are initially at least a distance of 10-100 from the walls.
- The walls form a simple, valid quadrilateral without straight angles.
Input: 3 0 -4 0 4 2 2 2 -2 -2 -2 -2 2 0 0 0 4 2 2 -2 2 -2 -2 2 -2 -1 3 1 3 -2 0 0 4 2 0 0 11 Output: 9.6568542495 -1 2.82842712475
In the first test case, there are two shortest paths: either go by the left or right of the castle walls.
|Tags||acm16, admin3, geometry, icpc16, kgp16, mathspuzzle, point_in_polygon|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions