Problem Statement |
| | A segment can be represented as a pair of four integers (x1, y1, x2, y2), where (x1, y1) are the coordinates of its starting point and (x2, y2) are the coordinates of its ending point. In this problem, you will be given a set of n segments, all of which are either parallel to or form a 45 degree angle with one of the axes. Your task is to count the number of unique triangles resulting from their intersection. Two triangles are considered to be different if and only if they share at most two common vertices.
You will be given a int[] X1, a int[] Y1, a int[] X2 and a int[] Y2 such that each 4-uple of the form (X1[i], Y1[i], X2[i], Y2[i]) denotes a segment. Return an int representing the number of triangles resulting from the segments' intersection.
|
| |
Definition |
| | | Class: | HiddenTriangles | | Method: | howMany | | Parameters: | int[], int[], int[], int[] | | Returns: | int | | Method signature: | int howMany(int[] X1, int[] Y1, int[] X2, int[] Y2) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | X1, Y1, X2 and Y2 each contain between 0 and 50 elements, inclusive. |
| - | X1, Y1, X2 and Y2 have the same number of elements. |
| - | All segments must either be parallel to or form a 45 degree angle with one of the axes. |
| - | Each segment has length at least 1. |
| - | All elements are between -100 and 100, inclusive. |
| |
Examples |
| 0) | |
| | {0,0,0,0,0,3} | {0,0,0,3,3,0} | {3,0,3,3,3,3} | {0,3,3,0,3,3} |
| Returns: 8 | There are four triangles of area 2.25 and another four of area 4.5.
 |
|
|
| 1) | |
| | {0,1,0,2,1,2,0,1,2,0,0,0} | {0,0,1,0,0,1,0,0,0,2,1,0} | {2,2,1,0,0,1,0,1,2,2,2,2} | {2,1,2,2,1,2,2,2,2,2,1,0} |
| Returns: 44 | |
|
| 2) | |
| | {0,1,2,0,0,0} | {0,0,0,2,1,0} | {0,1,2,2,2,2} | {2,2,2,2,1,0} |
| Returns: 0 | This is a set of perpendicular lines forming a square divided into four smaller squares. No triangles can be made.
 |
|
|
| 3) | |
| | |
| 4) | |
| | {-50,-40,-30,-20,-10,0,10,20,30,40,50,-100,-100,5,6,7,20} | {0,0,0,0,0,0,0,0,0,0,0,25,75,8,8,8,0} | {-50,-40,-30,-20,-10,0,10,20,30,40,50,100,100,55,56,57,-40} | {100,100,100,100,100,100,100,100,100,100,100,25,75,58,58,58,60} |
| Returns: 31 | |
|
| 5) | |
| | {0,0,10,9,8,7,6,5,4,3,2,1} | {0,0,0,1,2,3,4,5,6,7,8,9} | {10,0,9,8,7,6,5,4,3,2,1,0} | {0,10,1,2,3,4,5,6,7,8,9,10} |
| Returns: 1 | |
|