ASCII Art
Time limit2sMemory limit128 MB
Compute the exact overlap area of a simple polygon with each unit grid cell using polygon clipping and map the fraction to a character to render ASCII art.
- Level
Medium7 of 10
- Topics
- Geometry, Simulation, Implementation
- Solved
- No attempts yet
Problem
ASCII art represents pictures using characters and symbols. In this problem, we use a simplified version.
There is a rectangular grid of width w and height h. Its lower-left corner is (0, 0), and its upper-right corner is (w, h). For integers x and y with 0 <= x < w and 0 <= y < h, a pixel is the unit square whose opposite corners are (x, y) and (x + 1, y + 1).
One simple polygon is drawn on the grid. The polygon does not have to be convex, but it does not cross or touch itself.
For each pixel, compute the fraction of that pixel's area that lies inside the polygon. Convert the fraction to a character using the following rules.
- At least 0% and less than 25%:
. - At least 25% and less than 50%:
+ - At least 50% and less than 75%:
o - At least 75% and less than 100%:
$ - Exactly 100%:
#
Print the ASCII art obtained by applying these rules to every pixel of the grid.
Input
The first line contains three integers n, w, and h, separated by spaces. Here n is the number of vertices of the polygon, and w and h are the width and height of the grid.
Each of the next n lines contains two integers x_i and y_i, the coordinates of one polygon vertex. The vertices are given in clockwise order.
All of n, w, and h are positive integers at most 100. Every vertex satisfies 0 <= x_i <= w and 0 <= y_i <= h.
Output
Print h lines from the top row (y = h - 1) down to the bottom row (y = 0). Each line must contain w characters from left to right.