PROBLEM LINK:
Author: Chandan Boruah
Tester: Taranpreet Singh
Editorialist: TaranPreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Slope of a line, Observation.
PROBLEM:
Given N lines represented by two points, we need to find maximum number of lines which can pass through a single point, without superimposing any other line. we can move any line but not rotate it.
QUICK EXPLANATION
- Represent lines as pair (m, c) where line can be given as y = mx+c, called line slope form. We can now see that we can change the c for any line, but cannot modify m.
-
Lines with Same value of slope ($m$) are parallel to each other, given ($c_{1} \neq c_{2}$). -
No two parallel lines can pass through same point without superimposing each other. -
Our problem reduces to finding different values of slopes from the given set of lines.
EXPLANATION
The quick Explanation says it all. 
We can calculate slope of a line as (y_2 - y_1)/(x_2-x_1), add them to a set and count the number of distinct values of slope in set.
BUT BUT, what about REs we were getting in contest??
This was because of some lines having x_1 = x_2, test case specially added by devil tester :D, which caused arithmetic Division by zero error.
We need to handle vertical (and probably horizontal too, if we wish) lines separately. Maybe having two boolean values horizontal and vertical would do fine. Each boolean value indicate whether input set contains a vertical (or horizontal) line.
If true, would each of them contribute 1 to final answer.
Complexity:
Time Complexity is O(N).
AUTHOR’S SOLUTIONS:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int t=int.Parse(Console.ReadLine());
while((t--)>0)
{
int n=int.Parse(Console.ReadLine());
int[]x1=new int[n];
int[]y1=new int[n];
int[]x2=new int[n];
int[]y2=new int[n];
for(int i=0;i<n;i++)
{
string[]ss=Console.ReadLine().Split();
x1[i]=int.Parse(ss[0]);
y1[i]=int.Parse(ss[1]);
x2[i]=int.Parse(ss[2]);
y2[i]=int.Parse(ss[3]);
}
SortedSet<double>slopes=new SortedSet<double>();
for(int i=0;i<n;i++)
{
double slope=0;
if(y1[i]==y2[i])
{
slope=int.MaxValue;
}
else
slope=(x1[i]-x2[i])*1.0/(y1[i]-y2[i]);
if(!slopes.Contains(slope))
{
slopes.Add(slope);
}
}
Console.WriteLine(slopes.Count);
}
}
}