Intersect | Topcoder Archive

Problem Statement

You are searching for a new house. Location, location, location. You have identified a number of desirable attributes, and for each have sketched a rectangular area that contains all the locations that have that attribute.

You want it all. You need to find the area that is contained in every one of your rectangles. Create a class Intersection that contains a method area that takes as input the collection of rectangles and returns the area of their common intersection.

The collection of rectangles is given by a int[] x and a int[] y. The first two values of x and y specify opposing corners of one rectangle, the next two specify opposing corners of the next rectangle, etc. Thus, each rectangle is the region between its two x values and between its two y values.

Definition

Class:: Intersect
Method:: area
Parameters:: int[], int[]
Returns:: int
Method signature:: int area(int[] x, int[] y)
(be sure your method is public)

Notes

the 2 values of x (and of y) for a given rectangle are not necessarily given in ascending order

Constraints

x contains an even number of elements between 2 and 50 inclusive
y contains the same number of elements as x
each element of x and y is between -10,000 and 10,000 inclusive

Examples

```
{0,2,3,-4}
```
```
{17,1000,18,6}
```
```
Returns: 2
```
There are 2 rectangles, one having diagonally opposed corners (0,17) and (2,1000) and the other having diagonally opposed corners (3,18) and (-4,6). The common intersection is the region bounded by x=0, x=2, y=17, y=18 which is a rectangle 2 units wide and 1 unit tall.
```
{10000,-10000}
```
```
{-10000,10000}
```
```
Returns: 400000000
```
There is just one rectangle, so the answer is the area of that rectangle.
```
{3,8,6,12,10,15}
```
```
{7,17,7,17,7,17}
```
```
Returns: 0
```
The first two rectangles intersect each other, and the second and third rectangles intersect each other, but no area is contained in all three rectangles.

{0,0,0,0,0,0,0,0}

{5,5,5,5,5,5,5,5}

Returns: 0

Here we have 4 empty rectangles.

{2,100,5,32,1000,-20,47,12}

{29,-1000,-800,-200,-900,300,-600,-650}

Returns: 1000

{1,7,12,3,16,8,3,12}

{-90,-60,-70,3,-60,-90,-80,-100}

Returns: 0

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.