2013
11-11

# Circle Drawing

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 Xsize by Ysize 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 (xc, yc) and radius R is a set of pixels (x, y) satisfying the inequality (x − xc)2 + (y − yc)2 ≤ R2

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 contains numbers Xsize Ysize N followed by N sets of numbers xi yi Ri ci, describing the coordinates of center, radius and color of i-th circle.

1 <= Xsize, Ysize <= 1000, 1 <= N <= 10000, 0 <= xi < Xsize, 0 <= yi < Ysize, 1 <= Ri <= 212, 0 <= ci <= 9.

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

5 5 1
2 2 1 3


00000
00300
03330
00300
00000


This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
class circle{
int x,y,r,color;
}
class Set{
int n,m;
int next[][] = new int[1010][1010];
void init(int _n,int _m){
for(n=0;n<=_n;++n) for(m=0;m<=_m;++m)
next[n][m] = m;
n = _n;
m = _m;
}
public int find(int x,int y){
if(next[x][y]==y) return y;
return next[x][y] = find(x,next[x][y]);
}
}
public class Main {
static final int N = 1000+10,M = 1000000+10;
static int Graph[][] = new int[N][N];
static int que[] = new int[M],n,m,k;
static circle cir[] = new circle[10009];
static Set set = new Set();
static void start(){
for(int i=0;i< 10009;++i) cir[i] = new circle();
}
public static void main(String[]args) throws Exception{

int i;
start();

while(cin.nextToken()!=StreamTokenizer.TT_EOF){
m = (int) cin.nval;
cin.nextToken();
n = (int) cin.nval;
cin.nextToken();
k = (int) cin.nval;
for(i=0;i< k;++i){
cin.nextToken();
cir[i].y = (int)cin.nval;
cin.nextToken();
cir[i].x = (int)cin.nval;
cin.nextToken();
cir[i].r = (int)cin.nval;
cin.nextToken();
cir[i].color = (int)cin.nval;
}
solve();
}
}

static void draw(int x,int y,int r,int color){
int i,j,start,end,ret;
for(i=-r;i<=r;++i)if(i+x>=0 && i+x< n){
ret = r*r-i*i;
if(ret< 0) continue;
else ret = (int) Math.sqrt(ret);

start = Max(y-ret,0);
end = Min(m-1,y+ret);
for(j=start;j<=end;j=set.find(x+i, j)){
if(set.next[x+i][j]==j){
Graph[x+i][j] = color;
set.next[x+i][j] = j+1;
}
}
}
}

static int Max(int a,int b){
return a>b?a:b;
}

static int Min(int a,int b){
return a< b?a:b;
}

static void solve(){
int i,j;
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
for(i=0;i<=n;++i) for(j=0;j<=m;++j) Graph[i][j] = 0;
set.init(n, m);
for(i=k-1;i>=0;--i){
draw(cir[i].x,cir[i].y,cir[i].r,cir[i].color);
}
for(i=0;i< n;++i){
for(j=0;j< m;++j)
out.print(Graph[i][j]);
out.println();
}
out.flush();
}

}