Connection Status:
Competition Arena > OneMorePoint

OneMorePoint

SRM 278 · 2005-12-19 · by Vedensky

SRM 278 · 2005-12-19 · by Vedensky · Brute Force
Class Name: OneMorePoint
Return Type: String
Method Name: interiorPoint
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There are some rectangles on a plane. Determine whether a point exists such that above, below, to the left, and to the right of the point lies an interior point of a rectangle. This point must not lie inside or on the boundary of any of the given rectangles.

You are given a String[] rectangles, each element of which is formatted as "X1 Y1 X2 Y2", where X1 and Y1 are the coordinates of the lower left corner of a rectangle, and X2 and Y2 are the coordinates of the upper right corner. You are to return a String, "YES" if such a point exists and "NO" otherwise.

Notes

  • Point A(xa, ya) is above point B(xb, yb) if xa = xb and ya > yb.
  • Point A(xa, ya) is below point B(xb, yb) if xa = xb and ya < yb.
  • Point A(xa, ya) is to the left of point B(xb, yb) if xa < xb and ya = yb.
  • Point A(xa, ya) is to the right of point B(xb, yb) if xa > xb and ya = yb.

Constraints

  • rectangles will contain between 0 and 50 elements, inclusive.
  • Each element of rectangles will be formatted as "X1 Y1 X2 Y2".
  • X1, Y1, X2, and Y2 will each be an integer between 0 and 10000, inclusive, with no extra leading zeros.
  • X2 will be greater than X1, and Y2 will be greater than Y1.
Examples
0)
{"0 0 2 1", "2 0 3 2", "1 2 3 3", "0 1 1 3"}
Returns: "YES"

The given rectangles are shown in grey in this figure. Any white point will meet our requirements.

1)
{"0 0 2 1", "2 0 3 2", "1 2 3 3", "0 1 1 3", "1 1 2 2"}
Returns: "NO"
2)
{"0 0 2 1", "3 0 4 2", "2 3 4 4", "0 2 1 3"}
Returns: "NO"
3)
{"0 0 100 1", "100 1 200 2", "0 0 1 100", "50 50 51 51"}
Returns: "YES"
4)
{"1 1 1000 1000"}
Returns: "NO"

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

Coding Area

Language: C++17 · define a public class OneMorePoint with a public method string interiorPoint(vector<string> rectangles) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous