首页 > 专题系列 > Java解POJ > POJ 2383 Circle Drawing [解题报告] Java
2013
11-11

POJ 2383 Circle Drawing [解题报告] Java

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();
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
 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();
 }
	
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。