Code vita first Question " A "

please any could tell me how to solve Triangle problem. Please provide any hint or tell me the idea to solve the problem.

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

4 Likes

Yeah i need solution of second problem of tcs mockvita.

4 Likes

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.

What was the problem? I can’t remember.

What was the problem?

yaa…sure
here is the code for this problem but i solve it using python . you can understand the logic behind this code and can implement in any other language.
code:

from array import *
N=int(input())
line=[]*N
line=list(map(int,input().split()))
A=array(‘i’,line)
count=0

for i in range(0,N):
for j in range(i+1,N):
for k in range(j+1,N):
if(A[i]!=A[j] and A[i]!=A[k] and A[k]!=A[j]):
count+=1
print(count)