How to count maximum points on same line in Java

In this section, we are going to learn how to count points that lie on the same line. So, for points to be lying on the same line, the slope needs to be the same. The idea of slope comes from the fact that every point belonging to the same line must satisfy the condition of  y=mx+c, where m is a slope, c is a constant, and (x,y) are coordinate pairs.

Approach to the Problem:

We can solve this simply by finding a slope i.e (y2-y1)/(x2-x1). But the problem, in this case, is that if the value of (y2-y1)/(x2-x1) is less than unity, then the slope tends to zero, that’s the result in a fallacy. So, to overcome this we will be using an inbuilt math function i.e “Math. atan”, that will take care of the above problem. So, the catch of this problem is that whenever we calculate the slope, we need to cast it as double, otherwise the integer value will result in a wrong answer. And afterward, we will be using HashMap to store the slope and the slope count pairs. The time complexity of our solution will be O(n^2).

 
  //Driving Code
	public static void main(String[] args) {
	int count=0;	
	int a[] = {-1, 0, 1, 2, 3, 3};
	int b[] = {1, 0, 1, 2, 3, 4};
	
	count=MaximumPoints(a,b);
	System.out.print("Maximum points that lie on a Line is "+count);
	}
	
	public static int MaximumPoints(int a[],int b[]) {
		HashMap<Double,Integer> map = null;
		int count=0,ov=0,same = 0,max_curr = 0;
		double slope=0,x,y;
		for (int i=0;i<a.length;i++) {
			map=new HashMap<>();
			same=0;
			count=0;
			for(int j=i;j<b.length;j++) {
				if(i==j) 
					same++;
				else{
					if(a[j]-a[i]==0) {
					slope=Integer.MAX_VALUE;
					continue;
					}
				
				//System.out.print(b[j]-b[i]+" ");
				//System.out.print( a[j]-a[i]+" ");
					else {
						x = a[j] - a[i];
						y = b[j]- b[i];
						slope = Math.atan(y / x);}
					//System.out.println();
						if(map.containsKey(slope)) {
							ov=map.get(slope);
							map.put(slope, ov+1);
						}
						else map.put(slope, 1);
				//System.out.print(slope+" ");
				//System.out.println();
			}
				
			//System.out.print(map);	
			Set<Map.Entry<Double,Integer>> entries=map.entrySet();
				for(Map.Entry<Double,Integer> entry:entries) {
					count=Math.max(count,entry.getValue());
				}
			 max_curr = Math.max(max_curr,count+same);
			}
		}
		return max_curr;
		
	}

 

Output  :

Maximum points that lie on a Line is  4

 

Leave a Reply

Your email address will not be published. Required fields are marked *