Programming Geek
Rated 4.7/5 based on 1446 reviews

MockVita 2018 Problem: Triangles


Problem Description

A number (N) of lines (extending to infinity) in both directions are drawn on a plane. The lines are specified by the angle (positive or negative) made with the x-axis (in degrees). It may be assumed that the different lines are not coincident (they do not overlap each other) and that no three of them are concurrent (no three of them pass through the same point).
The objective is to determine the number of triangles formed by the set of these lines
If the lines are given with an angle of 10, 70, 30 and 30, the figure looks like this

L1 is at 10 degrees to the x axis, L2 is at 70 degrees to the x axis, L3 and L4 are at 30 degrees to the x-axis. It can be seen that there are two triangles (L1,L2,L3 and L1,L2,L4). L3 and L4 do not meet as they are parallel.
-89 <= angle for any line <=90
Input Format
The first line of the input consists of a single integer, N.
The next line consists of a series of integers (positive, zero or negative), each corresponding to a separate line, and giving the angle that it makes with the x-axis (measured in degrees and in the anticlockwise direction).
The output is a single integer giving the number of triangles formed by the lines
Test Case
TestCase 1 8,3 D,C,E,F,G,H C,A,E D,C,B,E A,B TestCase 2 8,3 D,C,E,F,G,H C,A,B,E D,B N/A


Example 1
There are 5 lines, with angles at 20,-20,0, 50 and 50 degrees with the x-axis. The figure looks like this

There are 7 triangles, those formed by (L1,L2,L3),(L1,L2,L5), (L1,L2,L4), (L1,L3,L4), (L1,L3,L5), (L2,L3,L5), (L2,L3,L4). Hence the output is 7.
Example 2
There are 5 lines with angles 50,-50,50,-50 and 50 degrees. The figure looks like this

As L1,L3 and L5 are parallel, and L2 and L4 are parallel, no triangles are formed by any set of three lines. Hence, the output is 0.

No comments :

Post a Comment