CareerCup

use O(nlogn) time to sort those rectangles by an axis (say, X), and then:
use O(n) time to find the set of intersected rectangles along the axis.

Use O(nlogn) time to sort by another axis(now it is Y), and then the same, use O(n) time to find the sec of intersected rectangles along Y axis.

Finally, use O(n) time to find the intersection of the two sets.

its a comp geometric problem....see line intersection algos

Can anyone please let me know how the input is given here?
I mean, are co-ordinates of the rectangle given or a two dimensional array indicating vertices of the rectangle is given???

Occasionally problems ask us to find the intersection of rectangles. There are a number of ways to represent a rectangle. For the standard Cartesian plane, a common method is to store the coordinates of the bottom-left and top-right corners.

Suppose we have two rectangles R1 and R2. Let (x1, y1) be the location of the bottom-left corner of R1 and (x2, y2) be the location of its top-right corner. Similarly, let (x3, y3) and (x4, y4) be the respective corner locations for R2. The intersection of R1 and R2 will be a rectangle R3 whose bottom-left corner is at (max(x1, x3), max(y1, y3)) and top-right corner at (min(x2, x4), min(y2, y4)). If max(x1, x3) > min(x2, x4) or max(y1, y3) > min(y2, y4) then R3 does not exist, ie R1 and R2 do not intersect.

source:

www[dot]topcoder[dot]com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

if i find mid points of x and y axis of every rectangle..

sort them

check if every 2 consecutive rectangle intersect!!

This Problem can be solved by representing the all the rectangle co-ordinates in the form of "Augmenting Height Balanced Trees" and finding the intersections by moving a sweep line across.