TopCoder problem "OneMorePoint" used in SRM 278 (Division I Level Two)



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.

 

Definition

    
Class:OneMorePoint
Method:interiorPoint
Parameters:String[]
Returns:String
Method signature:String interiorPoint(String[] rectangles)
(be sure your method is public)
    
 

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"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5924

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8075&pm=5924

Writer:

Vedensky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force