please any could tell me how to solve Triangle problem. Please provide any hint or tell me the idea to solve the problem.
What was the problem? I can’t remember.
please provide a link or at least description of the problem
The constraints are so small that you can iterate through all possible triplets and count number of triangles. Three lines can form a triangle iff the slopes of the three lines are pairwise distict.
1 Like
please provide all problems of mockvita
3 Likes
Yeah i need solution of second problem of tcs mockvita.
4 Likes
What was the problem?
Special Triangles
Problem Description
When we have 4 lines in the plane, the maximum number of triangles formed by them is 4 as shown below:
Of the four triangles ABF, CDF, BDE, ACE, triangles BDE and CDF are somewhat “special”. They do not have another of the given lines go through their interiors.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@601c7012:image1.png
Given n lines in the plane, the objective is to count the number of special triangles formed by them. You may assume that no three lines will be concurrent (go through the same point). Each line will be specified by two points (x and y coordinates of two points on the line).
Note that three lines may not form a triangle, let alone a special triangle, if two of them are parallel lines.
Constraints
N<=15
Each of the x and y coordinates of the points defining any line lies between -10 and 10.
Input Format
The first line will have a single integer, N, representing the number of lines in the input.
The next N lines will have four comma separated numbers representing x1, y1, x2, y2 (the x and y coordinates of the two points on the line.
Output
The output is a single line giving the number of special triangles formed.
Explanation
Example 1
Input
4
1,2,4,7
2,3,2,5
3,5,7,5
4,7,3,4
Output
2
Explanation
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@601c7012:image2.png
Line I is defined by the points (1,2) (A) and (4,7) (B). Similarly, line II is defined by C (2,3) and D (2,5), line III by E (3,5) and F(7,5) and line IV by B (4,7) and G (3,4).
Of the four triangles formed by the four lines, the ones by (I,II,III) and (I,III,IV) are special.
(I,II,IV) has III going through the interior, while (II,III,IV) has I going through the interior.
As only two triangles are special, the output is 2.
Example 2
Input
4
2,2,3,2
2,3,3,3
2,4,3,4
2,5,3,5
Output
0
Explanation
As all lines are parallel to the x axis, there are no triangles, and hence no special triangles. The output is 0.