CareerCup

Assuming no 2 lines are parallel we get t = C(n,3) triangles.

Now find the slopes of all lines.

If k lines have same slope, we need to reject p triangles where p can be calculated.

p = C(k,3) + C(k,2)*(n-k)

Find the summation of p for all such subsets of same slope

Triangles = n - Sum(p)

Is the solution C(n,3)? Choosing any 3 lines from n (assuming that all the lines intersect every other line) should give the number of triangles.

1. For lines they're parall, they should only count as 1
2. If we have n lines, after eliminating the parallel lines, we get k lines
3. The triages are k-2.

Forgot to mention, you have to give the line equation in polar system (R, Theta), e.g.
R = x*Cos(Theta) + Y*(SinTheta)

so easy... C(n, 3)

i am a bit confused.if 3 lines intersect at a point then how then can form a triangle.

1 -Find the slope of all the lines and sort them to identify parallel lines
2 -So if out of n we found k parallel lines then we are left with n-k lines which will intersect each other
3- No of triangles formed by these n-k lines is C(n-k, 3) which is say N
4- (I am not 100% sure about this step)Now out of those k lines if I pick a line so now my number of triangle should be 2*N so I think for each parallel line I add my number of triangles gets double. I checked this on some base cases and it seems working but not sure if this logic is full proof or not.

Desginate each line by a 2-tuple {startpt, endpt}
Sort by startpt.
Sort by end pt.
Do a O(n^2) forward pass of the startpt sorted set to find if pt i intersect with any of pts 0 <= j < i. If there are intersections save them in a set.
Do a O( n^2 ) reverse pass of the end pt sorted set to find if pt i intersect with any of pts i < j <= n-1. As before save any intersections in a set
Observation a triangle is possibly formed if set 1 has members like {1,2} while set 2 has members like {2,3}. So for element in set 1 do a scan of set 2 searching for these matches and then checking if they form a valid triangle.
O(n^2) , i think we can make the last step nlg n but creating sets 1 and 2 require n^2.

1. hash each line by slope and increment count for slope
2. max possible triangles = n C 3
3. for each slope having >1 count (i.e. > 1 lines with same slope) let x be number of lines with same slope. Then number of triangles which can't be formed because of parallelism of these x lines is equal to

(n-x) * (x C 2) + (x C 3)

4. Repeat process for all slopes and deduct exclusion count from n C 3

I think nc3 should be the answer when there are points in plane and not n lines. i can't think of scenario to create 4C3 (4) triangles with 4 lines.

1. let p1, p2,...pk be the parallel lines. for all parallel lines, we have to consider 1 line.
2. actual number of intersecting lines are
c = n-k (1 for p1, 1 for p2 and so on for pk)
3. triangles for c lines are c-2

4. now with each set of parallel lines, we can create the traingles, so final count is
(c -2 ) + (p1-1) + (p2-1) + ... + (pk-1)

please note that it ignores the smaller triangles as part of bigger triangles...
hope i'm clear

i think nC3

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: this doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: this doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: This doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: This doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: This doesn't consider small traingles being part of bigger triangles

Here you go :)
Code is in C# .Net

public class Point
{
public double x;
public double y;

public Point(double _x, double _y)
{
x = _x;
y = _y;
}
}

class PointComparer : IEqualityComparer<Point>
{
public bool Equals(Point x, Point y)
{
return x.x == y.x && y.y == x.y;
}

public int GetHashCode(Point x)
{

return 0;
}
}
public static int TriCounter()
{
List<double[]> Lines;
double[] Line1 = new double[2] { 0, Math.PI / 2 };
double[] Line2 = new double[2] { 0, 0 };
double[] Line3 = new double[2] { 10 * Math.Sqrt(2) / 2, - Math.PI / 4 };
double[] Line4 = new double[2] { 5 * Math.Sqrt(2) / 2, - 3 * Math.PI / 4 };

Lines = new List<double[]>();
Lines.Add(Line1);
Lines.Add(Line2);
Lines.Add(Line3);
Lines.Add(Line4);

HashSet<Point> intersection = new HashSet<Point>();
for (int i = 0; i < Lines.Count; i++)
{
for (int j = 0; j < Lines.Count; j++)
{
if (j != i)
{

double r1 = Lines[i][0];
double r2 = Lines[j][0];

double theta1 = Lines[i][1];
double theta2 = Lines[j][1];

double yIntersection = ((r1 / Math.Cos(theta1)) - (r2 / Math.Cos(theta2))) / (Math.Tan(theta1) - Math.Tan(theta2));

double x1 = (r1 - yIntersection * Math.Sin(theta1)) / Math.Cos(theta1);
double x2 = (r2 - yIntersection * Math.Sin(theta2)) / Math.Cos(theta2);

if (Math.Abs(x1 - x2) < 0.5)
{
yIntersection *= 1000;
yIntersection = (int)(yIntersection);
x1 *= 1000;
x1 = (int)(x1);

yIntersection /= 1000;
x1 /= 1000;

if (Math.Abs(yIntersection) < 0.00001) yIntersection = 0;
if (Math.Abs(x1) < 0.00001) x1 = 0;


if (!intersection.Contains<Point>(new Point(x1, yIntersection), new PointComparer()))
intersection.Add(new Point(x1, yIntersection));
}

}
}
}


int triCounter = 0;
for (int i = 0; i < intersection.Count; i++)
{
for (int j = 0; j < intersection.Count; j++)
{
for (int k = 0; k < intersection.Count; k++)
{
if (i != j && j != k)
{
Point first = intersection.ElementAt<Point>(i);
Point second = intersection.ElementAt<Point>(j);
Point third = intersection.ElementAt<Point>(k);

if (isOnSameLine(Lines, new double[] { first.x, first.y }, new double[] { second.x, second.y }) &&
isOnSameLine(Lines, new double[] { first.x, first.y }, new double[] { third.x, third.y }) &&
isOnSameLine(Lines, new double[] { third.x, third.y }, new double[] { second.x, second.y }))
{
triCounter++;
}
}
}
}
}

return triCounter / 3;
}
public static bool isOnSameLine(List<double[]> Lines, double[] point1, double[] point2)
{
for (int i = 0; i < Lines.Count; i++)
{
double y1 = Lines[i][0] * point1[0] + Lines[i][1];
double y2 = Lines[i][0] * point2[0] + Lines[i][1];

if (y1 == point1[1] && y2 == point2[1])
{
return true;
}
}

return false;
}