Problem Statement |
| | You are given n distinct straight lines in the plane. The i-th line is specified by two distinct lattice points (x1[i], y1[i]) and (x2[i], y2[i]) that lie on it. These lines divide the plane into regions, and your task is to compute and return the number of finite regions among them. By a finite region we mean a convex polygon bounded by the given lines, with no points belonging to any of the given lines in its interior. |
| |
Definition |
| | | Class: | PlaneDivision | | Method: | howManyFiniteParts | | Parameters: | int[], int[], int[], int[] | | Returns: | int | | Method signature: | int howManyFiniteParts(int[] x1, int[] y1, int[] x2, int[] y2) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | By a lattice point (x, y) we mean a point on the Cartesian plane with integer coordinates x and y. |
| - | Two points are said to be distinct if either their x-coordinates or y-coordinates differ. |
| |
Constraints |
| - | x1, y1, x2 and y2 will contain the same number of elements. |
| - | x1, y1, x2 and y2 will contain between 1 and 50 elements, inclusive. |
| - | All the elements of x1, y1, x2 and y2 will be between -10000 and 10000, inclusive. |
| - | (x1[i], y1[i]) and (x2[i], y2[i]) will be distinct for all i (i.e., every two points defining a given line will be distinct). |
| - | All the lines defined by (x1[i], y1[i]) and (x2[i], y2[i]) will be distinct. |
| |
Examples |
| 0) | |
| | | Returns: 0 | | A single line divides the plane into two infinite regions. |
|
|
| 1) | |
| | {0, 1, 2} | {0, 1, -1} | {1, 2, 0} | {1, -1, 0} |
| Returns: 1 | | The three lines are the sidelines of a triangle which is the only finite region in this case. |
|
|
| 2) | |
| | {-10000, -9999, 10000, -9999, 0, 500, -500} | {-9999, 10000, 9999, -10000, 0, 0, 0} | {-10000, 9999, 10000, 9999, 0, 500, -500} | {9999, 10000, -9999, -10000, 1, -1, -2} |
| Returns: 4 | | The only finite regions are the 4 big rectangles. |
|
|
| 3) | |
| | {0, 0, 0, 0, 0, 0, 0, 0, 0} | {0, 0, 0, 0, 0, 0, 0, 0, 0} | {1, 1, 1, 1, 1, 1, 1, 1, 1} | {1, 2, 3, 4, 5, 6, 7, 8, 9} |
| Returns: 0 | | All the lines pass through the origin. |
|
|
| 4) | |
| | {-1, -1, -1, -1, 1, 3, -3} | {-1, -2, 0, 0, 10000, 1, -5} | {1, 1, 1, -1, 1, -3, 3} | {1, 0, 2, -10000, 0, -2, 4} |
| Returns: 7 | | 1 parallelogramm and 6 triangles are the only finite regions in this case. |
|
|
| 5) | |
| | {-100, -100, -100, -100, -100} | {-100, -99, -98, -97, -96} | {100, 100, 100, 100, 100} | {99, 100, 101, 102, 103} |
| Returns: 0 | | 5 parallel lines do not produce any finite regions. |
|
|
| 6) | |
| | {-100, -100, -100, -100, -100, 1} | {-100, -99, -98, -97, -96, -1} | {100, 100, 100, 100, 100, -2} | {99, 100, 101, 102, 103, 2} |
| Returns: 0 | | A configuration of 5 parallel lines and a single line crossing all of them again yields no finite regions. |
|
|