Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- import java.math.*;
- public class Main {
- private BufferedReader in;
- private PrintWriter out;
- private StringTokenizer st;
- private Random rnd;
- int sortedAnglesPointer = 0, sortedRsPointer = 0;
- double[] sortedAngles;
- int[] sortedRs;
- ArrayList<Segment> sortedByStart, sortedByEnd;
- HashSet<Double> angles;
- HashSet<Integer> rs;
- boolean sortByEnd = false;
- final double inf = Double.MAX_VALUE;
- class Segment implements Comparable<Segment> {
- int r1, r2, phi1Id, phi2Id;
- double phi1, phi2;
- Segment(double _phi1, double _phi2, int _r1, int _r2) {
- r1 = _r1;
- r2 = _r2;
- phi1 = _phi1;
- phi2 = _phi2;
- }
- void setIds() {
- phi1Id = Arrays.binarySearch(sortedAngles, phi1);
- phi2Id = Arrays.binarySearch(sortedAngles, phi2);
- }
- public int compareTo(Segment o) {
- if(!sortByEnd) {
- return this.r1 - o.r1;
- } else {
- return this.r2 - o.r2;
- }
- }
- }
- public void addToAngles(double angle) {
- if(!angles.contains(angle)) {
- angles.add(angle);
- sortedAngles[sortedAnglesPointer++] = angle;
- }
- }
- public void addToRs(int r) {
- if(!rs.contains(r)) {
- rs.add(r);
- sortedRs[sortedRsPointer++] = r;
- }
- }
- double getSize(int l, int r) {
- return sortedAngles[r + 1] - sortedAngles[l];
- }
- class SegmentTree {
- int size;
- int[] level, add;
- double[] total;
- SegmentTree(int _size) {
- size = _size;
- level = new int[4 * size];
- add = new int[4 * size];
- total = new double[4 * size];
- }
- void push(int v, int l, int r) {
- if(add[v] != 0) {
- level[2 * v + 1] += add[v];
- level[2 * v + 2] += add[v];
- add[2 * v + 1] += add[v];
- add[2 * v + 2] += add[v];
- add[v] = 0;
- int m = (l + r) / 2;
- recalc(2 * v + 1, l, m);
- recalc(2 * v + 2, m + 1, r);
- }
- }
- void recalc(int v, int l, int r) {
- if(level[v] > 0) {
- total[v] = getSize(l, r);
- } else {
- total[v] = 0;
- }
- }
- void update(int v, int l, int r, int from, int to, int mod) {
- if(from == l && to == r) {
- level[v] += mod;
- add[v] += mod;
- recalc(v, l, r);
- return;
- }
- push(v, l, r);
- int m = (l + r) / 2;
- if(from <= m) {
- update(2 * v + 1, l, m, from, Math.min(m, to), mod);
- }
- if(to > m) {
- update(2 * v + 2, m + 1, r, Math.max(m + 1, from), to, mod);
- }
- total[v] = total[2 * v + 1] + total[2 * v + 2];
- }
- double get(int v, int l, int r, int from, int to) {
- if(from == l && to == r) {
- return total[v];
- }
- push(v, l, r);
- int m = (l + r) / 2;
- double res = 0.0;
- if(from <= m) {
- res += get(2 * v + 1, l, m, from, Math.min(m, to));
- }
- if(to > m) {
- res += get(2 * v + 2, m + 1, r, Math.max(m + 1, from), to);
- }
- return res;
- }
- }
- public void solve() throws IOException {
- double start = System.currentTimeMillis();
- int n = nextInt();
- sortedAngles = new double[2 * n + 2];
- sortedRs = new int[2 * n];
- Arrays.fill(sortedRs, Integer.MAX_VALUE);
- sortedByStart = new ArrayList<Segment>(n);
- sortedByEnd = new ArrayList<Segment>(n);
- angles = new HashSet<Double>();
- rs = new HashSet<Integer>();
- addToAngles(0);
- addToAngles(2 * Math.PI);
- for(int i = 0; i < n; i++) {
- double phi1 = nextDouble(), phi2 = nextDouble();
- int r1 = nextInt(), r2 = nextInt();
- if(phi1 < phi2) {
- sortedByStart.add(new Segment(phi1, phi2, r1, r2));
- sortedByEnd.add(new Segment(phi1, phi2, r1, r2));
- } else {
- sortedByStart.add(new Segment(phi1, 2.0 * Math.PI, r1, r2));
- sortedByStart.add(new Segment(0, phi2, r1, r2));
- sortedByEnd.add(new Segment(phi1, 2.0 * Math.PI, r1, r2));
- sortedByEnd.add(new Segment(0, phi2, r1, r2));
- }
- addToAngles(phi1);
- addToAngles(phi2);
- addToRs(r1);
- addToRs(r2);
- }
- Arrays.sort(sortedAngles);
- Arrays.sort(sortedRs);
- Collections.sort(sortedByStart);
- sortByEnd = true;
- Collections.sort(sortedByEnd);
- int Segments = sortedByStart.size();
- for(int i = 0; i < Segments; i++) {
- sortedByStart.get(i).setIds();
- sortedByEnd.get(i).setIds();
- }
- SegmentTree t = new SegmentTree(sortedAnglesPointer);
- int startPointer = 0, endPointer = 0;
- double res = 0;
- /* Идём по радиусам, поддерживая в дереве отрезков сегменты с этим радиусом */
- for(int i = 0; i < sortedRsPointer - 1; i++) {
- int curR = sortedRs[i];
- int nextR = sortedRs[i + 1];
- /* Убираем из дерева отрезков кончившиеся сегменты */
- while(endPointer < Segments && sortedByEnd.get(endPointer).r2 <= curR) {
- //out.println("Remove:" + " " + sortedByEnd.get(endPointer).phi1 + " " + sortedByEnd.get(endPointer).phi2);
- //out.println(sortedByEnd.get(endPointer).phi1Id + " " + sortedByEnd.get(endPointer).phi2Id);
- t.update(0, 0, sortedAnglesPointer - 1, sortedByEnd.get(endPointer).phi1Id, sortedByEnd.get(endPointer).phi2Id - 1, -1);
- ++endPointer;
- }
- /* Добавляем начавшиеся */
- while(startPointer < Segments && sortedByStart.get(startPointer).r1 == curR) {
- //out.println("Added:" + " " + sortedByStart.get(startPointer).phi1 + " " + sortedByStart.get(startPointer).phi2);
- //out.println(sortedByStart.get(startPointer).phi1Id + " " + sortedByStart.get(startPointer).phi2Id);
- t.update(0, 0, sortedAnglesPointer - 1, sortedByStart.get(startPointer).phi1Id, sortedByStart.get(startPointer).phi2Id - 1, 1);
- ++startPointer;
- }
- /* Считаем площадь */
- double curS = t.get(0, 0, sortedAnglesPointer - 1, 0, sortedAnglesPointer - 1);
- double r1 = curR * curR;
- double r2 = nextR * nextR;
- res += curS * (r2 - r1);
- }
- res /= 2.0;
- out.println(res);
- out.println((System.currentTimeMillis() - start) / 1000.0);
- }
- public static void main(String[] args) {
- new Main().run();
- }
- public void run() {
- try {
- //in = new BufferedReader(new FileReader("bigbadnumber.in"));
- //out = new PrintWriter(new FileWriter("bigbadnumber.out"));
- in = new BufferedReader(new InputStreamReader((System.in)));
- out = new PrintWriter(System.out);
- st = null;
- rnd = new Random();
- solve();
- out.close();
- } catch(IOException e) {
- e.printStackTrace();
- }
- }
- private String nextToken() throws IOException, NullPointerException {
- while(st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine());
- }
- return st.nextToken();
- }
- private int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- private long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- private double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment