Poj Solution 2383

http://poj.org/problem?id=2383

//* @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();
 }
    
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *