﻿

# City Park

a guest
Dec 12th, 2019
132
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.io.*;
2. import java.util.*;
3.
4. public class K {
5.
6.     public static void main(String[] args) {
8.         PrintWriter out = new PrintWriter(System.out);
10.         int t = 1;
11.         while (t --> 0) solver.solve(1, scan, out);
12.         out.close();
13.     }
14.
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<>();
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];
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();
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) {
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<>();
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.
119.         StringTokenizer st;
120.
123.         }
124.
125.         public FastReader(String s) throws FileNotFoundException {
127.         }
128.
129.         String next() {
130.             while (st == null || !st.hasMoreElements()) {
131.                 try {
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 {