RectangleCrossings
SRM 373 · 2007-10-23 · by Vedensky
SRM 373 · 2007-10-23 · by Vedensky · Brute Force, Geometry, String Parsing
Problem Statement
Problem Statement
There are some rectangles and line segments on the plane. You must compute two values: the total area of the rectangles that contain at least one endpoint of a line segment, and the total area of the rectangles that do not contain any endpoints but are intersected by one or more line segments.
The sides of the rectangles are parallel to the coordinate axes. No two rectangles intersect. This means no two rectangles share any common points (including their borders). A line segment intersects a rectangle if they share at least one common point. This common point can be a segment's endpoint or a point on the rectangle's border. A rectangle contains a point if it lies within the boundary of the rectangle and does not lie on its border. See examples for further clarification.
You are given aString[] rectangles, each element of which is formatted as "X1 Y1 X2 Y2" (quotes for clarity), where (X1, Y1) are the coordinates of the lower left corner of a rectangle and (X2, Y2) are the coordinates of its upper right corner. You are also given a String[] segments, each element of which is formatted as "X1 Y1 X2 Y2", where (X1, Y1) and (X2, Y2) are the two endpoints of a line segment. Return a int[] containing the two values described above, in the given order.
The sides of the rectangles are parallel to the coordinate axes. No two rectangles intersect. This means no two rectangles share any common points (including their borders). A line segment intersects a rectangle if they share at least one common point. This common point can be a segment's endpoint or a point on the rectangle's border. A rectangle contains a point if it lies within the boundary of the rectangle and does not lie on its border. See examples for further clarification.
You are given a
Constraints
- rectangles and segments will each contain between 0 and 50 elements, inclusive.
- Each element of rectangles and segments will be formatted as "X1 Y1 X2 Y2" (quotes for clarity).
- X1, Y1, X2, and Y2 will each be an integer between -1000 and 1000, inclusive, with no extra leading zeros.
- In each element of rectangles, X2 will be greater than X1, and Y2 will be greater than Y1.
- No two rectangles will intersect. This means no two rectangles will share any common points (including their borders).
- No segment will have zero length.
Examples
0)
{"-1000 -1000 1000 1000"}
{"-525 245 222 243"}
Returns: {4000000, 0 }
The only rectangle contains both ends of the only segment.
1)
{"1 1 2 2", "1 4 2 5", "5 5 6 7", "7 7 9 9"}
{"1 2 1 5"}
Returns: {0, 2 }
The only segment intersects rectangles 0 and 1.
2)
{"1 1 3 3", "4 4 5 5", "6 6 7 7", "8 8 9 9", "51 22 344 352", "-124 -235 -12 -1"}
{"-100 -2 300 300"}
Returns: {122898, 0 }
The first four rectangles are not intersected by the segment.
3)
{"1 1 3 3", "4 4 5 5", "6 6 7 7", "8 8 9 9", "51 22 344 352", "-124 -235 -12 -1"}
{"-104 -103 202 201"}
Returns: {122898, 7 }
The first four rectangles are intersected by the segment.
4)
{"-1000 -1000 1000 1000"}
{"-141 -755 -123 -135", "-321 -545 -123 -135", "311 235 777 543", "1 1 423 53"}
Returns: {4000000, 0 }
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RectangleCrossings with a public method vector<int> countAreas(vector<string> rectangles, vector<string> segments) · 57 test cases · 2 s / 256 MB per case