Connection Status:
Competition Arena > Intersect

Intersect

SRM 160 · 2003-08-23 · by dgoodman

SRM 160 · 2003-08-23 · by dgoodman · Geometry
Class Name: Intersect
Return Type: int
Method Name: area
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{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.

1)
{10000,-10000}
{-10000,10000}
Returns: 400000000

There is just one rectangle, so the answer is the area of that rectangle.

2)
{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.

3)
{0,0,0,0,0,0,0,0}
{5,5,5,5,5,5,5,5}
Returns: 0

Here we have 4 empty rectangles.

4)
{2,100,5,32,1000,-20,47,12}
{29,-1000,-800,-200,-900,300,-600,-650}
Returns: 1000

Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Intersect with a public method int area(vector<int> x, vector<int> y) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous