HiddenTriangles
SRM 239 · 2005-04-18 · by supernova
SRM 239 · 2005-04-18 · by supernova · Geometry
Problem Statement
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.
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.
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)
{}
{}
{}
{}
Returns: 0
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
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HiddenTriangles with a public method int howMany(vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2) · 34 test cases · 2 s / 256 MB per case