Author: | Elena Andreeva (original idea), Roman Elizarov (text) | Time limit: | 2 sec | |
Input file: | find.in | Memory limit: | 64 Mb | |
Output file: | find.out |
Closed polyline (with possible self-intersections) partitions a plane into a number of regions. One of the regions is unbounded — it is an exterior of the polyline. All the bounded regions together with the polyline itself form an interior of the polyline (shaded in the picture below). The border of the interior (bold line in the picture) is a polyline as well. This polyline has the same interior as the original one. Your task is to find the border of the interior of the given polyline.
To guarantee the uniqueness (up to the starting point) of the polyline representing the border we require that the following conditions are satisfied for it:
- it has no self-intersections, although may have self-touchings;
- no adjacent vertices of the border coincide;
- no adjacent edges of the border are collinear;
- when traversing the border, its interior is always to the left of its edges.
No. | Input file (find.in ) |
Output file (find.out ) |
---|---|---|
1 |
|
|