/** * Attempt at NAIPC 2019 Rectangles * * @author godmar@gmail.com */ import java.io.*; import java.util.*; import static java.lang.Math.*; public class Rectangles_godmar { public static void main(String av[]) { Scanner s = new Scanner(); int n = s.nextInt(); Rectangle [] rect = new Rectangle[n]; for (int i = 0; i < n; i++) { rect[i] = new Rectangle(s.nextInt(), s.nextInt(), s.nextInt(), s.nextInt()); } System.out.println(new Rectangles_godmar().solve(rect, n)); } static class Rectangle { int x1, y1, x2, y2, s; Rectangle(int x1, int y1, int x2, int y2) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } public String toString() { return String.format("(%d,%d)-(%d,%d)", x1, y1, x2, y2); } } /** * Line Sweep Events. * Events are processed by increasing x coordinate. */ static enum EventType { ENTER, LEAVE }; static abstract class Event implements Comparable { int x; EventType type; Event(int x, EventType type) { this.x = x; this.type = type; } @Override public int compareTo(Event that) { int byX = Integer.compare(this.x, that.x); if (byX != 0) return byX; return Integer.compare(this.type.ordinal(), that.type.ordinal()); } abstract boolean process(); } int solve(Rectangle []rect, int n) { List events = new ArrayList<>(); TreeMap iv = new TreeMap<>(); for (int i = 0; i < n; i++) { final Rectangle r = rect[i]; events.add(new Event(r.x1, EventType.ENTER) { boolean process() { // // +--------- // | // --+----+ // | | // +----+---- // | // --------+ Map.Entry e = iv.floorEntry(r.y1); if (e != null) { int yj = e.getValue(); if (r.y1 < yj && yj < r.y2) { return true; } } // +-------- // | // ---+----+ // | | // | | // ---+----+ // | // +----+---- e = iv.ceilingEntry(r.y1); if (e != null) { int yi = e.getKey(); int yj = e.getValue(); if (r.y1 < yi && yj < r.y2 || r.y1 < yi && yi < r.y2) return true; } iv.put(r.y1, r.y2); return false; } }); events.add(new Event(r.x2, EventType.LEAVE) { boolean process() { // // +--------- // | // ---+----+ // | | // +----+---- // | // --------+ // // --------+ // | // +----+---- // + + // +----+---- // | // --------+ iv.remove(r.y1); Map.Entry e = iv.ceilingEntry(r.y1); if (e != null) { int yi = e.getKey(); int yj = e.getValue(); if (r.y1 < yi && yj < r.y2 || yi < r.y2 && r.y2 < yj) return true; } return false; } }); } Collections.sort(events); // now line sweep for (Event e : events) if (e.process()) return 1; return 0; } //-----------Scanner class for faster input---------- /* Provides similar API as java.util.Scanner but does not * use regular expression engine. */ public static class Scanner { BufferedReader br; StringTokenizer st; public Scanner(Reader in) { br = new BufferedReader(in); } public Scanner() { this(new InputStreamReader(System.in)); } 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()); } // Slightly different from java.util.Scanner.nextLine(), // which returns any remaining characters in current line, // if any. String readNextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } //-------------------------------------------------------- }