Advertisement
Guest User

City Park

a guest
Dec 12th, 2019
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.09 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class K {
  5.  
  6.     public static void main(String[] args) {
  7.         FastReader scan = new FastReader();
  8.         PrintWriter out = new PrintWriter(System.out);
  9.         Task solver = new Task();
  10.         int t = 1;
  11.         while (t --> 0) solver.solve(1, scan, out);
  12.         out.close();
  13.     }
  14.  
  15.     static class Task {
  16.         static int n;
  17.         static long[] area;
  18.         static HashMap<Long, ArrayList<Interval>> verticalInterval = new HashMap<>();
  19.         static HashMap<Long, ArrayList<Interval>> horizontalInterval = new HashMap<>();
  20.         static ArrayList<Integer>[] adj;
  21.         static boolean[] visited;
  22.  
  23.         public void solve(int testNumber, FastReader scan, PrintWriter out) {
  24.             int n = scan.nextInt();
  25.             area = new long[n];
  26.             adj = new ArrayList[n];
  27.             visited = new boolean[n];
  28.             long ans = 0;
  29.  
  30.             for(int i = 0; i < n; i++) {
  31.                 long x = scan.nextLong(), y = scan.nextLong(), x2 = x + scan.nextLong(), y2 = y + scan.nextLong();
  32.                 adj[i] = new ArrayList<>();
  33.                 area[i] = (x2-x)*(y2-y);
  34.                 addInterval(x, y, y2, verticalInterval, i);
  35.                 addInterval(x2, y, y2, verticalInterval, i);
  36.                 addInterval(y, x, x2, horizontalInterval, i);
  37.                 addInterval(y2, x, x2, horizontalInterval, i);
  38.             }
  39.             for(long x : verticalInterval.keySet()) {
  40.                 createConnections(verticalInterval.get(x));
  41.             }
  42.             for(long y : horizontalInterval.keySet()) {
  43.                 createConnections(horizontalInterval.get(y));
  44.             }
  45.             for(int i = 0; i < n; i++) {
  46.                 if(!visited[i]) ans = Math.max(ans, findArea(i));
  47.             }
  48.             out.println(ans);
  49.         }
  50.  
  51.         static long findArea(int curr) {
  52.             long ans = area[curr];
  53.             visited[curr] = true;
  54.             for(int i : adj[curr]) {
  55.                 if(!visited[i]) ans += findArea(i);
  56.             }
  57.             return ans;
  58.         }
  59.  
  60.         static void createConnections(ArrayList<Interval> curr) {
  61.             Collections.sort(curr);
  62.             Interval total = curr.get(0);
  63.             for(int i = 1; i < curr.size(); i++) {
  64.                 Interval now = curr.get(i);
  65.                 if(total.end >= now.start) {
  66.                     adj[total.index].add(now.index);
  67.                     adj[now.index].add(total.index);
  68.                     total.end = Math.max(total.end, now.end);
  69.                 }
  70.                 else total = now;
  71.             }
  72.         }
  73.  
  74.         static void addInterval(long a, long b, long c, HashMap<Long, ArrayList<Interval>> h, int i) {
  75.             ArrayList<Interval> curr = h.containsKey(a) ? h.get(a) : new ArrayList<>();
  76.             curr.add(new Interval(b, c, i));
  77.             if(!h.containsKey(a)) h.put(a, curr);
  78.         }
  79.  
  80.         static class Interval implements Comparable<Interval> {
  81.             long start, end;
  82.             int index;
  83.  
  84.             public Interval(long a, long b, int c) {
  85.                 start = a;
  86.                 end = b;
  87.                 index = c;
  88.             }
  89.             @Override
  90.             public int compareTo(Interval o) {
  91.                 if(start == o.start) return Long.compare(o.end, end);
  92.                 return Long.compare(start, o.start);
  93.             }
  94.         }
  95.     }
  96.  
  97.     static void shuffle(int[] a) {
  98.         Random get = new Random();
  99.         for (int i = 0; i < a.length; i++) {
  100.             int r = get.nextInt(a.length);
  101.             int temp = a[i];
  102.             a[i] = a[r];
  103.             a[r] = temp;
  104.         }
  105.     }
  106.  
  107.     static void shuffle(long[] a) {
  108.         Random get = new Random();
  109.         for (int i = 0; i < a.length; i++) {
  110.             int r = get.nextInt(a.length);
  111.             long temp = a[i];
  112.             a[i] = a[r];
  113.             a[r] = temp;
  114.         }
  115.     }
  116.  
  117.     static class FastReader {
  118.         BufferedReader br;
  119.         StringTokenizer st;
  120.  
  121.         public FastReader() {
  122.             br = new BufferedReader(new InputStreamReader(System.in));
  123.         }
  124.  
  125.         public FastReader(String s) throws FileNotFoundException {
  126.             br = new BufferedReader(new FileReader(new File(s)));
  127.         }
  128.  
  129.         String next() {
  130.             while (st == null || !st.hasMoreElements()) {
  131.                 try {
  132.                     st = new StringTokenizer(br.readLine());
  133.                 } catch (IOException e) {
  134.                     e.printStackTrace();
  135.                 }
  136.             }
  137.             return st.nextToken();
  138.         }
  139.  
  140.         int nextInt() {
  141.             return Integer.parseInt(next());
  142.         }
  143.  
  144.         long nextLong() {
  145.             return Long.parseLong(next());
  146.         }
  147.  
  148.         double nextDouble() {
  149.             return Double.parseDouble(next());
  150.         }
  151.  
  152.         String nextLine() {
  153.             String str = "";
  154.             try {
  155.                 str = br.readLine();
  156.             } catch (IOException e) {
  157.                 e.printStackTrace();
  158.             }
  159.             return str;
  160.         }
  161.     }
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement