Polygon Expansion
Time limit1sMemory limit128 MB
Given a rectilinear simple polygon, compute the outward offset polygon by distance d, merging filled concave regions and outputting vertices in a fixed starting order.
- Level
Hard8 of 10
- Topics
- Geometry, Simulation, Implementation
- Solved
- No attempts yet
Problem
You are given a simple polygon made only of horizontal and vertical line segments. Its vertices are listed in counterclockwise order, and every pair of adjacent vertices forms one horizontal or vertical side.
The d-expansion of the polygon is the boundary of the region obtained by expanding every point on the polygon boundary outward by distance d. During this expansion, concave parts may be filled, so the expanded polygon may have a different number of vertices from the original polygon. You may assume that the expanded polygon has no holes.
Given d and the original polygon, write a program that computes the d-expanded polygon.
Input
The first line contains the integer d. The second line contains the number of vertices n. Each of the next n lines contains one vertex coordinate Xi Yi of the polygon, listed in counterclockwise order around the boundary.
The constraints are as follows.
- 1 <= d <= 500
- 3 <= n <= 50
- Every X and Y coordinate is a positive integer not greater than 2000.
Output
On the first line, print the number of vertices of the expanded polygon. Then print the coordinates of the expanded polygon, one vertex per line.
Start with the vertex with the smallest x-coordinate; if there are several such vertices, start with the one among them with the smallest y-coordinate. Print the remaining vertices in counterclockwise order.