2043 Area of Polygons

「2043 Area of Polygons」の編集履歴（バックアップ）一覧はこちら

「2043 Area of Polygons」(2006/04/17 (月) 02:06:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2043 Area of Polygons
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2043
**解答方針
どのマスが塗りつぶされるかを，1行ずつ（つまり，y座標ごとに）調べていきます．多角形のうちy+EPSILONとy+1-EPSILONにはさまれた部分は複数の台形からなるので，各台形によって塗りつぶされるマスを調べていけばよいわけです．EPSILONは誤差対策のための小さな数です．
**解答例
 import java.util.*;
 
 public class Main{
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             //read input
             int n = sc.nextInt();
             if(n==0) break;
             int xmin = Integer.MAX_VALUE;
             int ymin = Integer.MAX_VALUE;
             int xmax = Integer.MIN_VALUE;
             int ymax = Integer.MIN_VALUE;
             Point[] p = new Point[n+1];
             for(int i=0;i<n;i++){
                 int x = sc.nextInt();
                 int y = sc.nextInt();
                 if(x<xmin) xmin = x;
                 if(x>xmax) xmax = x;
                 if(y<ymin) ymin = y;
                 if(y>ymax) ymax = y;
                 p[i] = new Point(x,y);
             }
             p[n] = p[0];
             
             // standardize
             for(int i=0;i<n;i++){
                 p[i].x -= xmin;
                 p[i].y -= ymin;
             }
             xmax = xmax - xmin;
             ymax = ymax - ymin;
             
             //solve
             Solver sol = new Solver(n,p,xmax,ymax);
             System.out.println(sol.solve());
         }
     }
 }
 
 class Solver{
     int n;
     Point[] p;
     int xmax;
     int ymax;
     final static double EPSILON = 1E-5;
     
     Solver(int n, Point[] p, int xmax, int ymax) {
         this.n = n;
         this.p = p;
         this.xmax = xmax;
         this.ymax = ymax;
     }
     public int solve(){
         int ret = 0;
 
         for(int y=0;y<ymax;y++){
             ArrayList<Double> intersect0 = new ArrayList<Double>();
             ArrayList<Double> intersect1 = new ArrayList<Double>();
             
             for(int i=0;i<n;i++){
                 int y0 = p[i].y;
                 int y1 = p[i+1].y;
                 int x0 = p[i].x;
                 int x1 = p[i+1].x;
                 if(Math.min(y0,y1)<=y&&y+1<=Math.max(y0,y1)){
                     if(x0!=x1){
                         double lx0 = (x0*(y1-(y+EPSILON))+x1*((y+EPSILON)-y0))/(double)(y1-y0);
                         double lx1 = (x0*(y1-(y+1-EPSILON))+x1*((y+1-EPSILON)-y0))/(double)(y1-y0);
                         intersect0.add(lx0);
                         intersect1.add(lx1);
                     }
                     else/* x0==x1 */{
                         intersect0.add((double)x0);
                         intersect1.add((double)x0);
                     }
                 }
             }
             
             double[] array0 = new double[intersect0.size()];
             double[] array1 = new double[intersect1.size()];
             for(int i=0;i<array0.length;i++) array0[i] = intersect0.get(i);
             for(int i=0;i<array0.length;i++) array1[i] = intersect1.get(i);
             Arrays.sort(array0);
             Arrays.sort(array1);
             
             boolean count[] = new boolean[xmax];
             for(int i=0;i<xmax;i++) count[i] = false;
             
             for(int i=0;i<array0.length;i+=2){
                 int x0 = (int)Math.floor(Math.min(array0[i],array1[i]));
                 int x1 = (int)Math.ceil(Math.max(array0[i+1],array1[i+1])) - 1;
                 for(int x=x0;x<=x1;x++){
                     count[x] = true;
                 }
             }
             
             for(int i=0;i<xmax;i++) if(count[i]) ret++;
         }
         return ret;
     }
 }
 
 class Point{
     int x;
     int y;
     Point(int x, int y) {
         this.x = x;
         this.y = y;
     }
 }