CareerCup

My suggestion was to create a map with key pair<a, b> and value - number of points contained in line aX+b.
Then traverse each pair of points (Xi, Yi) (Xj Yj), send to the given function to receive a, b of the line connecting those two points
And update the map by adding 1 to the key <a,b> (creating it with value of 1 if not yet in the map).
In addition keeping aside the <a, b> for which the number of points is the highest.
Order of this solution is O(N^2)
I was wondering if there is a solution with better performance.

Your algorithm is O(N^2*lgN) { insertion in map is lgN }

Another approach:

ans = 0
For each point A:
       store all possible slopes with the remaining points in an array slopes[]
       sort the array slopes[] and now you can easily find the slope with max. occurence in this array i.e ans = MAX( ans, current_max occurence of slope )

ans gives you the final result

This method has same time complexity O(N^2lgN) but will be relatively faster due to much smaller constact factor. You may also try to hash the slopes and then find the max but hashing floating point values will be extra overhead.

first sort all points according to there polar angle i have given code for sorting point according to polar angle 

typedef struct point{
	int x;
	int y;
}point;

int cross_product(point a, point b){
	if((a.x*b.y-a.y*b.x)>0)
	return 1;
	return -1;
}

int partition(arr,p,r){
	point pivot = arr[r-1];
	int i=p,flag,j=-1;
	while(i<r-1){
		flag = cross_product(pivot,arr[i]);
		if(flag == 1){
			if(j==-1){
				j = p+1;
			}
			while(j<r-1){
				flag = cross_product(pivot,a[j])
				if(flag!=1){
					swap(arr[i],arr[j]);
					j=j+1;
					break	
				}
				j++;
			}
			if(j == r-1){
				swap(arr[i+1],arr[r])
				return(i+1);
				break
			}
			
		}
		i++;
	}
	swap(arr[i+1],arr[r])
	return(i+1);
	
}

void polar_sort(point arr[],int start,int end){
	
	int stack[end],top =-1,p,r,k;
	stack[++top] = start;
	stack[++top] = end;
	while(isEmpty(stack)){
	
		r = stack[top--];
		p = stack[top--];
		if(p<r){
			k = partition(arr,p,r);
			if(k+1<r){
				stack[++top] = k+1;
				stack[++top] = r;
			}
			if(p<k){
				stack[++top] = p;
				stack[++top] = k;
			}
		}
	
	}
	
}


in this way u sort the point according to polar angle now just we have to trverse this sorted point array and for comparing
,is they lie on same line or not do cross product and if cross product is 0 then yup they are in same line and as array is sorted 
according to polar angle, all points are in same line coming together just find max group whose cross product is 0 that u can do esily
in one traversal and for finding the line ,found two farthest point in the group and make a line with those two points

correct me if i m wrong complexity(nlogn)

First, choose pairs of points and find slope and intercept for each pair using the given function and add them to a map keyed by say "slope:intercept" and value as value+1 (count). The key with the highest count is the answer.

initialize linkedhashmap<point,<slope,count>> point_slope_counts
initialize linkedhashmap<slope,count> : point_slopes
1. for each point p
   1.i   clear 
   1.ii. for each other point q
       1.ii.a.   slope = (yq - yp)/(xq - xp) // possible error divide by 0, for lines ||lel to y axis
       1.ii.b    count = point_slopes.get(slope) // handle null
       1.ii.c    count += 1
       1.ii.d    point_slopes.put(count)
   1.iii. <slope.count> = argmax-count (point_slopes)
   1.iv. point_slope_counts.put(p,<slope,count>) // line with max points passing thru p
2. final_point <point,<slope,count>> = argmax-count (point_slope_counts)

This would be O(n^2).

initialize linkedhashmap<point,<slope,count>> point_slope_counts
initialize linkedhashmap<slope,count> : point_slopes
1. for each point p
   1.i   clear point_slopes
   1.ii. for each other point q
       1.ii.a.   slope = (yq - yp)/(xq - xp) // possible error divide by 0, for lines ||lel to y axis
       1.ii.b    count = point_slopes.get(slope) // handle null
       1.ii.c    count += 1
       1.ii.d    point_slopes.put(count)
   1.iii. <slope.count> = argmax-count (point_slopes)
   1.iv. point_slope_counts.put(p,<slope,count>) // line with max points passing thru p
2. final_point <point,<slope,count>> = argmax-count (point_slope_counts)

This would be O(n^2).

it looks like the problem "find the most common number in a list of numbers"

A line will have maximum points if they have same slope.

Its a DP problem for finding the maximum slope pair across all the points, Like Knapsack problem.

check my answer and if any mistakes are there suggest me..
#include<stdio.h>
char * eq(int x1,int y1,int x2,int y2);
main()
{
int x1,y1,x2,y2;
char *equ;
printf("enter 2 pts(x1,y1)&(x2,y2)\n");
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
equ=eq(x1,y1,x2,y2);
printf("%s\n",equ);
}
char * eq(int x1,int y1,int x2,int y2)
{
float sl;
sl=(x2-x1)/(y2-y1);
char equ[]="ax+y";
equ[0]=sl+48;
return(equ);
}

Apply the RANSAC algorithm with threshold = 0. In the worst case the number of choices is choose(n,2), however randomizing the choice of 2 points reduces the expected time complexity. This is the best that is done in line fitting.

Linear regression finds the line of best fit, it is NOT robust to outliers. RANSAC is the way to go here.