Aizu Online Judge 1202 Mobile Phone Coverage

■1202 Mobile Phone Coverage

面倒な問題．下の画像のような感じに分割した．区間をマージする処理が面倒だった．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  R[] rs;  
18.  int caze;  
19.   
20.  void run(){  
21.   for(caze=1;; caze++){  
22.    n=sc.nextInt();  
23.    if(n==0){  
24.     break;  
25.    }  
26.    rs=new R[n];  
27.    for(int i=0; i<n; i++){  
28.     double x=sc.nextDouble();  
29.     double y=sc.nextDouble();  
30.     double r=sc.nextDouble();  
31.     rs[i]=new R(x-r, y-r, x+r, y+r);  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  void solve(){  
38.   TreeSet<Double> setX=new TreeSet<Double>();  
39.   for(int i=0; i<n; i++){  
40.    setX.add(rs[i].x1);  
41.    setX.add(rs[i].x2);  
42.   }  
43.   Double[] xs=setX.toArray(new Double[0]);  
44.   sort(xs);  
45.   int m=xs.length;  
46.   @SuppressWarnings("unchecked")  
47.   TreeSet<R>[] setR=new TreeSet[m];  
48.   for(int i=0; i<m; i++){  
49.    setR[i]=new TreeSet<R>();  
50.   }  
51.   
52.   for(int j=0; j<m-1; j++){  
53.    for(int i=0; i<n; i++){  
54.     if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){  
55.      setR[j].add(rs[i]);  
56.     }  
57.    }  
58.   }  
59.   
60.   double sum=0;  
61.   for(int k=0; k<m-1; k++){  
62.    LinkedList<Double> seg=new LinkedList<Double>();  
63.    for(R r : setR[k]){  
64.     if(abs(r.y1-r.y2)<EPS){  
65.      continue;  
66.     }  
67.     int i=seg.size(), j=seg.size();  
68.     for(int p=seg.size()-1; p>=0; p--){  
69.      double y=seg.get(p);  
70.      if(y+EPS>r.y2){  
71.       j=p;  
72.      }  
73.      if(y+EPS>r.y1){  
74.       i=p;  
75.      }  
76.     }  
77.     for(int p=i; p<j; p++){  
78.      seg.remove(i);  
79.     }  
80.     if(j%2==0){  
81.      seg.add(i, r.y2);  
82.     }  
83.     if(i%2==0){  
84.      seg.add(i, r.y1);  
85.     }  
86.    }  
87.    double len=0;  
88.    for(int i=0; i<seg.size(); i+=2){  
89.     len+=seg.get(i+1)-seg.get(i);  
90.    }  
91.    sum+=len*(xs[k+1]-xs[k]);  
92.   }  
93.   println(String.format("%d %.2f", caze, sum+EPS));  
94.  }  
95.   
96.  class R implements Comparable<R>{  
97.   double x1, y1, x2, y2;  
98.   
99.   R(double x1, double y1, double x2, double y2){  
100.    this.x1=x1;  
101.    this.y1=y1;  
102.    this.x2=x2;  
103.    this.y2=y2;  
104.   }  
105.   
106.   @Override  
107.   public int compareTo(R arg0){  
108.    if(y1-y2+EPS<0){  
109.     return -1;  
110.    }else if(y1-y2>0+EPS){  
111.     return 1;  
112.    }else if(x1-x2+EPS<0){  
113.     return -1;  
114.    }else if(x1-x2>0+EPS){  
115.     return 1;  
116.    }else{  
117.     return 0;  
118.    }  
119.   }  
120.  }  
121.   
122.  void debug(Object... os){  
123.   // System.err.println(Arrays.deepToString(os));  
124.  }  
125.   
126.  void print(String s){  
127.   System.out.print(s);  
128.  }  
129.   
130.  void println(String s){  
131.   System.out.println(s);  
132.  }  
133.   
134.  public static void main(String[] args){  
135.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
136.   new Main().run();  
137.  }  
138. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 R[] rs;
 int caze;

 void run(){
  for(caze=1;; caze++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   rs=new R[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double r=sc.nextDouble();
    rs[i]=new R(x-r, y-r, x+r, y+r);
   }
   solve();
  }
 }

 void solve(){
  TreeSet<Double> setX=new TreeSet<Double>();
  for(int i=0; i<n; i++){
   setX.add(rs[i].x1);
   setX.add(rs[i].x2);
  }
  Double[] xs=setX.toArray(new Double[0]);
  sort(xs);
  int m=xs.length;
  @SuppressWarnings("unchecked")
  TreeSet<R>[] setR=new TreeSet[m];
  for(int i=0; i<m; i++){
   setR[i]=new TreeSet<R>();
  }

  for(int j=0; j<m-1; j++){
   for(int i=0; i<n; i++){
    if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){
     setR[j].add(rs[i]);
    }
   }
  }

  double sum=0;
  for(int k=0; k<m-1; k++){
   LinkedList<Double> seg=new LinkedList<Double>();
   for(R r : setR[k]){
    if(abs(r.y1-r.y2)<EPS){
     continue;
    }
    int i=seg.size(), j=seg.size();
    for(int p=seg.size()-1; p>=0; p--){
     double y=seg.get(p);
     if(y+EPS>r.y2){
      j=p;
     }
     if(y+EPS>r.y1){
      i=p;
     }
    }
    for(int p=i; p<j; p++){
     seg.remove(i);
    }
    if(j%2==0){
     seg.add(i, r.y2);
    }
    if(i%2==0){
     seg.add(i, r.y1);
    }
   }
   double len=0;
   for(int i=0; i<seg.size(); i+=2){
    len+=seg.get(i+1)-seg.get(i);
   }
   sum+=len*(xs[k+1]-xs[k]);
  }
  println(String.format("%d %.2f", caze, sum+EPS));
 }

 class R implements Comparable<R>{
  double x1, y1, x2, y2;

  R(double x1, double y1, double x2, double y2){
   this.x1=x1;
   this.y1=y1;
   this.x2=x2;
   this.y2=y2;
  }

  @Override
  public int compareTo(R arg0){
   if(y1-y2+EPS<0){
    return -1;
   }else if(y1-y2>0+EPS){
    return 1;
   }else if(x1-x2+EPS<0){
    return -1;
   }else if(x1-x2>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}