Charles University in Prague Technical University of Ostrava Slovak University of Technology Pavol Jozef Sˇaf´arik University in Koˇsice
University of Zˇilina Masaryk University Matej Bel University in Bansk´a Bystrica University of West Bohemia
train.c, train.cpp, Train.java, train.py
An aviary or a flight cage is a big cage for birds. An usual ZOO aviary typically measures tens of 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 | |||||
7.07105
2.00
1.00
0.00