training_2005_11_26 - Circle Drawing

Problem E. Circle Drawing ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	3 sec
Input file:	input.txt	Memory limit:	4 Mb
Output file:	output.txt

Statement

Graphics libraries usually implement drawing of graphics primitives, like lines, polygons and circles. Your task is to write a program that draws circles.

Graphic canvas is represented as an array of X_size by Y_size pixels. Each pixel have a color ranged from 0 to 9. Initially all pixels have color 0. Pixels are thought of as small sqares with the side of length 1. A circle with center (x_c, y_c) and radius R is a set of pixels (x, y) satisfying the inequality (x − x_c)² + (y − y_c)² ≤ R²

To draw a circle, your program should set the color of all pixels in a set defined above to the color of the circle. After drawing N given circles, the program should output the color of all pixels of the canvas.

Input file format

Input file contains numbers X_size Y_size N followed by N sets of numbers x_i y_i R_i c_i, describing the coordinates of center, radius and color of i-th circle.

Output file format

Output file should contain Y_size lines of X_size characters each, where i-th character of j-th line is a digit corresponding to color of the pixel (i, j).

Constraints

1 ≤ X_size, Y_size ≤ 1000, 1 ≤ N ≤ 10000, 0 ≤ x_i < X_size, 0 ≤ y_i < Y_size, 1 ≤ R_i ≤ 200, 0 ≤ c_i ≤ 9.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`5 5 1 2 2 1 3`	`00000 00300 03330 00300 00000`
2	`4 3 2 2 2 2 5 0 1 1 9`	`9050 9955 9555`