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 a String[] 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. |
| |
Definition |
| | | Class: | RectangleCrossings | | Method: | countAreas | | Parameters: | String[], String[] | | Returns: | int[] | | Method signature: | int[] countAreas(String[] rectangles, String[] segments) | | (be sure your method is public) |
|
| |
|
| |
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) | |
| | {"-891 -869 -853 -842", "-857 -399 -744 -231", "-910 -55 -856 36", "-844 287 -749 548", "-809 627 -782 954",
"-704 -803 -641 -663", "-684 -330 -558 -268", "-702 -40 -545 98", "-660 386 -528 586", "-697 855 -571 962",
"-414 -678 -168 -648", "-401 -559 -383 -441", "-387 5 -263 51", "-389 220 -194 448", "-361 673 -175 753",
"68 -912 95 -742", "-24 -521 24 -227", "30 -70 38 -2", "-111 297 14 356", "7 797 27 809", "368 -709 418 -614",
"247 -453 344 -251", "385 -111 417 -33", "275 202 290 421", "265 604 278 921", "524 -861 655 -640",
"555 -336 576 -305", "429 28 578 35", "480 324 704 520", "444 632 665 842", "932 -954 981 -931",
"930 -537 939 -455", "735 -81 787 192", "830 316 869 589", "808 629 971 666"} | {"-898 -383 126 12", "283 -716 545 -918", "-299 333 54 138", "-901 129 706 488", "-8 690 -290 955",
"-590 -771 476 257", "-528 -518 651 -139", "-984 -848 -380 459", "-358 924 31 -617", "817 -904 -208 -401",
"-657 -211 275 -407", "-427 -699 -460 876", "403 -612 -675 563", "-782 -197 845 816", "-492 -771 -342 -83",
"-650 -208 393 -614", "-67 -290 135 -610", "68 650 -366 560", "-482 608 -525 516", "548 460 -95 -436",
"461 -457 -491 -846", "-672 728 -764 548", "-301 633 -613 278", "-496 126 940 576", "-350 -378 -671 1000",
"148 82 275 211", "815 872 -810 -362", "160 -367 -754 569", "-721 941 -405 -57", "-792 582 804 563",
"-934 -115 -641 -737"} |
| Returns: {126942, 241757 } | |
|