Restore an Orthogonal Polygon
Time limit2sMemory limit128 MB
Given the unordered vertices of an orthogonal (axis-aligned) polygon, reconstruct the boundary order and output its perimeter length.
- Level
Medium6 of 10
- Topics
- Geometry, Sorting, Implementation
- Solved
- No attempts yet
Problem
An orthogonal polygon is a polygon whose every side is parallel to either the x-axis or the y-axis. Its boundary goes straight, then turns at right angles at its vertices.
You are given all vertices of an orthogonal polygon. The vertices may not be given in boundary order. Find the length of the boundary of the orthogonal polygon determined by the given vertices.
Input
The first line contains the number of points N. (1 <= N <= 100000)
Each of the next N lines contains two coordinates x and y of a point. (0 <= x, y <= 10000)
No point appears more than once. The input is guaranteed to consist only of vertices that form one orthogonal polygon.
Output
Print the boundary length of the orthogonal polygon on the first line.