Connection Status:
Competition Arena > TwoRectangles

TwoRectangles

SRM 546 · 2011-11-22 · by misof

SRM 546 · 2011-11-22 · by misof · Geometry, Simple Math
Class Name: TwoRectangles
Return Type: String
Method Name: describeIntersection
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given two rectangles in the plane. The sides of each rectangle are parallel to the coordinate axes. Each rectangle is given by the coordinates of its lower left corner and its upper right corner. You are given two int[]s: A and B. A describes the first rectangle: its lower left corner has coordinates (A[0],A[1]) and its upper right corner has coordinates (A[2],A[3]). B describes the second rectangle in the same way.

Your task is to determine how their intersection looks like. There are four options:

  • If the rectangles have a non-zero area in common, return "rectangle".
  • Otherwise, if they have a common line segment with non-zero length, return "segment".
  • Otherwise, if they have a point in common, return "point".
  • Otherwise, return "none" (in all four cases, the quotes are just for clarity).

Notes

  • The Constraints guarantee that both rectangles lie in the first quadrant of the coordinate plane, and each rectangle has a positive area.

Constraints

  • A will contain exactly 4 elements.
  • The elements of A will satisfy 0 <= A[0] < A[2] <= 1000 and 0 <= A[1] < A[3] <= 1000.
  • B will contain exactly 4 elements.
  • The elements of B will satisfy 0 <= B[0] < B[2] <= 1000 and 0 <= B[1] < B[3] <= 1000.
Examples
0)
{0,0,3,2}
{1,1,5,3}
Returns: "rectangle"

These two rectangles overlap partially:

1)
{0,0,5,3}
{1,2,2,3}
Returns: "rectangle"

The second rectangle is completely inside the first one.

2)
{1,1,6,2}
{3,2,5,4}
Returns: "segment"

The second rectangle sits on top of the first one.

3)
{0,1,2,3}
{2,0,5,2}
Returns: "segment"
4)
{0,0,1,1}
{1,1,5,2}
Returns: "point"

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

Coding Area

Language: C++17 · define a public class TwoRectangles with a public method string describeIntersection(vector<int> A, vector<int> B) · 226 test cases · 2 s / 256 MB per case

Submitting as anonymous