import java.io.PrintStream; import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; /** * Solution to Intersecting Rectangles * * @author vanb */ public class rectangles_vanb { /** The Input. */ private static Scanner sc; /** The Output. */ private static PrintStream ps; /** * A Fenwick Tree. */ private class FenwickTree { /** The number of things in the Fenwick Tree. */ int size; /** The Tree itself. */ int[] table; /** * Instantiates a new Fenwick Tree. * * @param size the size */ FenwickTree(int size) { this.size = size; table = new int[size]; } /** * Update an element of the Fenwick Tree. * * @param i the index of the element to update * @param delta the change in the value of table[i] */ void update(int i, int delta) { while (i < size) { table[i] += delta; i |= i+1; } } /** * Sum from 0 to i. * * @param i the index to sum up to * @return the sum */ int sum(int i) { int sum = 0; while (i >= 0) { sum += table[i]; i = (i&(i+1))-1; } return sum; } } /** * A Vertical edge of a Rectangle */ private class Edge implements Comparable { /** The lower y */ public int y1; /** The upper y. */ public int y2; /** The x. */ public int x; /** Is this a Leading Edge or a Trailing Edge? */ public boolean leading; /** * Instantiates a new edge. * * @param y1 the lower y * @param y2 the upper y * @param x the x * @param leading true if this is a Leading Edge */ public Edge( int y1, int y2, int x, boolean leading ) { this.y1 = y1; this.y2 = y2; this.x = x; this.leading = leading; } /** * @see java.lang.Comparable#compareTo(java.lang.Object) */ public int compareTo( Edge other ) { // Sort by x, then y1, then y2, then leading int diff = x - other.x; if( diff==0 ) diff = y1 - other.y1; if( diff==0 ) diff = y2 - other.y2; if( diff==0 ) diff = leading ? -1 : 1; return diff; } } /** * Doit. */ private void doit() { // Number of Rectangles int n = sc.nextInt(); // Read in the edges Edge edges[] = new Edge[n+n]; int ys[] = new int[n+n]; int c=0; for( int i=0; i ymap = new HashMap(n+n); Arrays.sort( ys ); for( int i=0; i fenwick.sum( edge.y1-1 ) ) { answer = 1; break; // No need to go any further } // If this is a leading edge, then it adds horizontal edges at y1 and y2 if( edge.leading ) { fenwick.update( edge.y1, 1 ); fenwick.update( edge.y2, 1 ); } } ps.println( answer ); } /** * The main method. * * @param args the arguments * @throws Exception the exception */ public static void main( String[] args ) throws Exception { sc = new Scanner( System.in ); ps = System.out; new rectangles_vanb().doit(); } }