1800. Visitors’ Train
时间限制 1000 ms 内存限制 128 MBof meters in diameter. In the aviaries, the birds can fly around and live in conditions imitating
the conditions in the wild as closely as possible. At least in theory. There is one main big and
spectacular aviary in the ZOO and some other less important ones.
The ZOO is planning to build a short straight electric train track to help visitors to move easily
from one part of the ZOO to another. It has to be decided which of the free areas of the ZOO
will the track run through. The director had noticed during his trips to other ZOOs that the
visitors are more happy when they can take more photos of important ZOO structures. Now
he wants to measure the quality of the planned railway by this parameter. The most important
structure in the vicinity of the track will be the main aviary. The director worries that the main
aviary might be obscured by the less important aviaries along the track and the visitors might
be less happy. Help the director to assess the quality of the planned track.
You are given the coordinates of all aviaries. Also, you are given the coordinates of the start and
the end of the planned railway track. Find the total length of the segments on the track from
which the main aviary is visible and is not obscured, even not partially, by any other aviary. We
suppose that the visitors can look out from the train in any direction.
输入数据
There are more test cases. Each case occupies more lines. The first line contains number N
(1 ≤ N ≤ 100) of the aviaries. Next line contains the coordinates of the planned railway track in
the format x1 y1 x2 y2 where [x1, y1] and [x2, y2] are the coordinates of the start and the end of
the track. The track is considered to be infinitely thin in this representation. Next, there are N
lines specifying the aviaries, each aviary is represented as a rectangle with nonzero area. Each
of these lines specifies the coordinates of an aviary in the form x1 y1 x2 y2 x3 y3 x4 y4, where
[x1, y1], [x2, y2], [x3, y3], and [x4, y4] are the coordinates of the aviary corners. The corners are
presented in clockwise or anti-clockwise order. The main aviary is listed first. All coordinates
are integers, their absolute value is less than 10 000. You may assume that no aviary intersects
or touches the track or another aviary. There is no blank line between consecutive test cases.
The input is terminated by a line with one zero.
输出数据
For each test case print on a separate line the total length L of all segments of the planned track
from which the main aviary is visible and it is not obscured, even not partially, by any other
aviary. Your answer should not differ from the correct answer by more than 10-4.
As shown in the third Sample Input, the main aviary is not considered obscured if only its
corners/edges are hidden.
样例输入
5 3 1 17 15 6 14 4 17 7 19 9 16 2 12 1 13 2 14 3 13 8 9 8 12 9 12 9 9 12 14 10 18 12 19 14 15 12 6 18 9 19 7 13 4 1 0 0 0 2 4 -1 4 1 5 1 5 -1 2 0 0 0 1 4 0 4 2 5 2 5 0 2 0 3 0 3 -1 2 -1 2 0 0 0 1 4 0 4 2 5 2 5 0 2 0 3 0 3 1 2 1 0\n · · · \n · · · · · · · \n · · · · · · · \n · · · · · · · \n · · · · · · · \n · · · · · · · \n \n · · · \n · · · · · · · \n \n · · · \n · · · · · · · \n · · · · · · · \n \n · · · \n · · · · · · · \n · · · · · · · \n \n
样例输出 special judge
7.071050 2.000000 1.000000 0.000000\n \n \n \n