Building a New Depot
Time limit1sMemory limit128 MB
Given the corner posts of an axis-aligned rectilinear polygon (listed in no particular order), reconstruct the polygon and compute its total perimeter.
- Level
Medium5 of 10
- Topics
- Geometry, Sorting, Hash map, Implementation
- Solved
- No attempts yet
Problem
A cargo transport company is expanding, and to keep up with the growing demand for truck maintenance it decided to build a new truck depot. The depot's lot is enclosed by a fence. The fence surrounds a single connected region, and every segment of the fence runs either North-South or East-West. A post is placed at each point where the fence changes direction, and nowhere else (there are no unnecessary posts).
After the workers finished putting up all the posts, they lost the construction plan. Given the coordinates of every post, compute the total length of the fence.
Input
The input consists of several blocks. The first line of each block contains the number of posts (). Each of the next lines contains two integers and (), the coordinates of one post. No two posts share the same coordinates.
Each block is followed by a single blank line, and the input ends with a line containing a single .
Output
For each block, print one line in exactly the form The length of the fence will be L units., where L is replaced by the actual length of the fence. You may assume the fence can always be built.