Guest User

Untitled

a guest
Sep 15th, 2011
268
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.91 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. public class Main {
  6.     private BufferedReader in;
  7.     private PrintWriter out;
  8.     private StringTokenizer st;
  9.     private Random rnd;
  10.    
  11.     int sortedAnglesPointer = 0, sortedRsPointer = 0;
  12.     double[] sortedAngles;
  13.     int[] sortedRs;
  14.     ArrayList<Segment> sortedByStart, sortedByEnd;
  15.     HashSet<Double> angles;
  16.     HashSet<Integer> rs;
  17.     boolean sortByEnd = false;
  18.    
  19.     final double inf = Double.MAX_VALUE;
  20.    
  21.     class Segment implements Comparable<Segment> {
  22.         int r1, r2, phi1Id, phi2Id;
  23.         double phi1, phi2;
  24.        
  25.         Segment(double _phi1, double _phi2, int _r1, int _r2) {
  26.             r1 = _r1;
  27.             r2 = _r2;
  28.             phi1 = _phi1;
  29.             phi2 = _phi2;
  30.         }
  31.        
  32.         void setIds() {
  33.             phi1Id = Arrays.binarySearch(sortedAngles, phi1);
  34.             phi2Id = Arrays.binarySearch(sortedAngles, phi2);
  35.         }
  36.        
  37.         public int compareTo(Segment o) {
  38.             if(!sortByEnd) {
  39.                 return this.r1 - o.r1;
  40.             } else {
  41.                 return this.r2 - o.r2;
  42.             }
  43.         }
  44.     }
  45.    
  46.     public void addToAngles(double angle) {
  47.         if(!angles.contains(angle)) {
  48.             angles.add(angle);
  49.             sortedAngles[sortedAnglesPointer++] = angle;
  50.         }
  51.     }
  52.    
  53.     public void addToRs(int r) {
  54.         if(!rs.contains(r)) {
  55.             rs.add(r);
  56.             sortedRs[sortedRsPointer++] = r;
  57.         }
  58.     }
  59.    
  60.     double getSize(int l, int r) {
  61.         return sortedAngles[r + 1] - sortedAngles[l];
  62.     }
  63.    
  64.     class SegmentTree {
  65.         int size;
  66.         int[] level, add;
  67.         double[] total;
  68.        
  69.         SegmentTree(int _size) {
  70.             size = _size;
  71.             level = new int[4 * size];
  72.             add = new int[4 * size];
  73.             total = new double[4 * size];
  74.         }
  75.        
  76.         void push(int v, int l, int r) {
  77.             if(add[v] != 0) {
  78.                 level[2 * v + 1] += add[v];
  79.                 level[2 * v + 2] += add[v];
  80.                 add[2 * v + 1] += add[v];
  81.                 add[2 * v + 2] += add[v];
  82.                
  83.                 add[v] = 0;
  84.                
  85.                 int m = (l + r) / 2;
  86.                 recalc(2 * v + 1, l, m);
  87.                 recalc(2 * v + 2, m + 1, r);
  88.             }
  89.         }
  90.        
  91.         void recalc(int v, int l, int r) {
  92.             if(level[v] > 0) {
  93.                 total[v] = getSize(l, r);
  94.             } else {
  95.                 total[v] = 0;
  96.             }
  97.         }
  98.        
  99.         void update(int v, int l, int r, int from, int to, int mod) {
  100.             if(from == l && to == r) {
  101.                 level[v] += mod;
  102.                 add[v] += mod;
  103.                 recalc(v, l, r);
  104.                 return;
  105.             }
  106.            
  107.             push(v, l, r);
  108.            
  109.             int m = (l + r) / 2;
  110.            
  111.             if(from <= m) {
  112.                 update(2 * v + 1, l, m, from, Math.min(m, to), mod);
  113.             }
  114.            
  115.             if(to > m) {
  116.                 update(2 * v + 2, m + 1, r, Math.max(m + 1, from), to, mod);
  117.             }
  118.            
  119.             total[v] = total[2 * v + 1] + total[2 * v + 2];
  120.         }
  121.        
  122.         double get(int v, int l, int r, int from, int to) {
  123.             if(from == l && to == r) {
  124.                 return total[v];
  125.             }
  126.            
  127.  
  128.             push(v, l, r);
  129.            
  130.             int m = (l + r) / 2;
  131.            
  132.             double res = 0.0;
  133.            
  134.             if(from <= m) {
  135.                 res += get(2 * v + 1, l, m, from, Math.min(m, to));
  136.             }
  137.            
  138.             if(to > m) {
  139.                 res += get(2 * v + 2, m + 1, r, Math.max(m + 1, from), to);
  140.             }
  141.            
  142.             return res;
  143.         }
  144.     }
  145.  
  146.     public void solve() throws IOException {
  147.         double start = System.currentTimeMillis();
  148.         int n = nextInt();
  149.        
  150.         sortedAngles = new double[2 * n + 2];
  151.         sortedRs = new int[2 * n];
  152.         Arrays.fill(sortedRs, Integer.MAX_VALUE);
  153.         sortedByStart = new ArrayList<Segment>(n);
  154.         sortedByEnd = new ArrayList<Segment>(n);
  155.         angles = new HashSet<Double>();
  156.         rs = new HashSet<Integer>();
  157.        
  158.         addToAngles(0);
  159.         addToAngles(2 * Math.PI);
  160.        
  161.         for(int i = 0; i < n; i++) {
  162.             double phi1 = nextDouble(), phi2 = nextDouble();
  163.             int r1 = nextInt(), r2 = nextInt();
  164.             if(phi1 < phi2) {
  165.                 sortedByStart.add(new Segment(phi1, phi2, r1, r2));
  166.                 sortedByEnd.add(new Segment(phi1, phi2, r1, r2));
  167.             } else {
  168.                 sortedByStart.add(new Segment(phi1, 2.0 * Math.PI, r1, r2));
  169.                 sortedByStart.add(new Segment(0, phi2, r1, r2));
  170.                 sortedByEnd.add(new Segment(phi1, 2.0 * Math.PI, r1, r2));
  171.                 sortedByEnd.add(new Segment(0, phi2, r1, r2));
  172.             }
  173.             addToAngles(phi1);
  174.             addToAngles(phi2);
  175.             addToRs(r1);
  176.             addToRs(r2);
  177.         }
  178.        
  179.        
  180.         Arrays.sort(sortedAngles);
  181.         Arrays.sort(sortedRs);
  182.         Collections.sort(sortedByStart);
  183.         sortByEnd = true;
  184.         Collections.sort(sortedByEnd);
  185.        
  186.         int Segments = sortedByStart.size();
  187.        
  188.         for(int i = 0; i < Segments; i++) {
  189.             sortedByStart.get(i).setIds();
  190.             sortedByEnd.get(i).setIds();
  191.         }
  192.        
  193.         SegmentTree t = new SegmentTree(sortedAnglesPointer);
  194.        
  195.         int startPointer = 0, endPointer = 0;
  196.         double res = 0;
  197.        
  198.         /* Идём по радиусам, поддерживая в дереве отрезков сегменты с этим радиусом */
  199.         for(int i = 0; i < sortedRsPointer - 1; i++) {
  200.             int curR = sortedRs[i];
  201.             int nextR = sortedRs[i + 1];
  202.            
  203.             /* Убираем из дерева отрезков кончившиеся сегменты */
  204.             while(endPointer < Segments && sortedByEnd.get(endPointer).r2 <= curR) {
  205.                 //out.println("Remove:" + " " + sortedByEnd.get(endPointer).phi1 + " " + sortedByEnd.get(endPointer).phi2);
  206.                 //out.println(sortedByEnd.get(endPointer).phi1Id + " " + sortedByEnd.get(endPointer).phi2Id);
  207.                 t.update(0, 0, sortedAnglesPointer - 1, sortedByEnd.get(endPointer).phi1Id, sortedByEnd.get(endPointer).phi2Id - 1, -1);
  208.                 ++endPointer;
  209.             }
  210.            
  211.             /* Добавляем начавшиеся */
  212.             while(startPointer < Segments && sortedByStart.get(startPointer).r1 == curR) {
  213.                 //out.println("Added:" + " " + sortedByStart.get(startPointer).phi1 + " " + sortedByStart.get(startPointer).phi2);
  214.                 //out.println(sortedByStart.get(startPointer).phi1Id + " " + sortedByStart.get(startPointer).phi2Id);
  215.                 t.update(0, 0, sortedAnglesPointer - 1, sortedByStart.get(startPointer).phi1Id, sortedByStart.get(startPointer).phi2Id - 1, 1);
  216.                 ++startPointer;
  217.             }
  218.            
  219.             /* Считаем площадь */
  220.             double curS = t.get(0, 0, sortedAnglesPointer - 1, 0, sortedAnglesPointer - 1);
  221.            
  222.             double r1 = curR * curR;
  223.             double r2 = nextR * nextR;
  224.            
  225.             res += curS * (r2 - r1);
  226.         }
  227.        
  228.         res /= 2.0;
  229.        
  230.         out.println(res);
  231.         out.println((System.currentTimeMillis() - start) / 1000.0);
  232.     }
  233.        
  234.     public static void main(String[] args) {
  235.         new Main().run();
  236.     }
  237.    
  238.     public void run() {
  239.         try {
  240.             //in = new BufferedReader(new FileReader("bigbadnumber.in"));
  241.             //out = new PrintWriter(new FileWriter("bigbadnumber.out"));
  242.            
  243.             in = new BufferedReader(new InputStreamReader((System.in)));
  244.             out = new PrintWriter(System.out);
  245.            
  246.             st = null;
  247.             rnd = new Random();
  248.            
  249.             solve();
  250.            
  251.             out.close();
  252.         } catch(IOException e) {
  253.             e.printStackTrace();
  254.         }
  255.     }
  256.    
  257.     private String nextToken() throws IOException, NullPointerException {
  258.         while(st == null || !st.hasMoreTokens()) {
  259.             st = new StringTokenizer(in.readLine());
  260.         }
  261.        
  262.         return st.nextToken();
  263.     }
  264.    
  265.     private int nextInt() throws IOException {
  266.         return Integer.parseInt(nextToken());
  267.     }
  268.    
  269.     private long nextLong() throws IOException {
  270.         return Long.parseLong(nextToken());
  271.     }
  272.    
  273.     private double nextDouble() throws IOException {
  274.         return Double.parseDouble(nextToken());
  275.     }
  276.  
  277. }
Advertisement
Add Comment
Please, Sign In to add comment