Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class K {
- public static void main(String[] args) {
- FastReader scan = new FastReader();
- PrintWriter out = new PrintWriter(System.out);
- Task solver = new Task();
- int t = 1;
- while (t --> 0) solver.solve(1, scan, out);
- out.close();
- }
- static class Task {
- static int n;
- static long[] area;
- static HashMap<Long, ArrayList<Interval>> verticalInterval = new HashMap<>();
- static HashMap<Long, ArrayList<Interval>> horizontalInterval = new HashMap<>();
- static ArrayList<Integer>[] adj;
- static boolean[] visited;
- public void solve(int testNumber, FastReader scan, PrintWriter out) {
- int n = scan.nextInt();
- area = new long[n];
- adj = new ArrayList[n];
- visited = new boolean[n];
- long ans = 0;
- for(int i = 0; i < n; i++) {
- long x = scan.nextLong(), y = scan.nextLong(), x2 = x + scan.nextLong(), y2 = y + scan.nextLong();
- adj[i] = new ArrayList<>();
- area[i] = (x2-x)*(y2-y);
- addInterval(x, y, y2, verticalInterval, i);
- addInterval(x2, y, y2, verticalInterval, i);
- addInterval(y, x, x2, horizontalInterval, i);
- addInterval(y2, x, x2, horizontalInterval, i);
- }
- for(long x : verticalInterval.keySet()) {
- createConnections(verticalInterval.get(x));
- }
- for(long y : horizontalInterval.keySet()) {
- createConnections(horizontalInterval.get(y));
- }
- for(int i = 0; i < n; i++) {
- if(!visited[i]) ans = Math.max(ans, findArea(i));
- }
- out.println(ans);
- }
- static long findArea(int curr) {
- long ans = area[curr];
- visited[curr] = true;
- for(int i : adj[curr]) {
- if(!visited[i]) ans += findArea(i);
- }
- return ans;
- }
- static void createConnections(ArrayList<Interval> curr) {
- Collections.sort(curr);
- Interval total = curr.get(0);
- for(int i = 1; i < curr.size(); i++) {
- Interval now = curr.get(i);
- if(total.end >= now.start) {
- adj[total.index].add(now.index);
- adj[now.index].add(total.index);
- total.end = Math.max(total.end, now.end);
- }
- else total = now;
- }
- }
- static void addInterval(long a, long b, long c, HashMap<Long, ArrayList<Interval>> h, int i) {
- ArrayList<Interval> curr = h.containsKey(a) ? h.get(a) : new ArrayList<>();
- curr.add(new Interval(b, c, i));
- if(!h.containsKey(a)) h.put(a, curr);
- }
- static class Interval implements Comparable<Interval> {
- long start, end;
- int index;
- public Interval(long a, long b, int c) {
- start = a;
- end = b;
- index = c;
- }
- @Override
- public int compareTo(Interval o) {
- if(start == o.start) return Long.compare(o.end, end);
- return Long.compare(start, o.start);
- }
- }
- }
- static void shuffle(int[] a) {
- Random get = new Random();
- for (int i = 0; i < a.length; i++) {
- int r = get.nextInt(a.length);
- int temp = a[i];
- a[i] = a[r];
- a[r] = temp;
- }
- }
- static void shuffle(long[] a) {
- Random get = new Random();
- for (int i = 0; i < a.length; i++) {
- int r = get.nextInt(a.length);
- long temp = a[i];
- a[i] = a[r];
- a[r] = temp;
- }
- }
- static class FastReader {
- BufferedReader br;
- StringTokenizer st;
- public FastReader() {
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- public FastReader(String s) throws FileNotFoundException {
- br = new BufferedReader(new FileReader(new File(s)));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- try {
- st = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- double nextDouble() {
- return Double.parseDouble(next());
- }
- String nextLine() {
- String str = "";
- try {
- str = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- return str;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement