6. Optimal location of point to minimize total distance

6. Optimal location of point to minimize total distance

Problem link :- click here

package program;

class Point
{
	//to create a set of points
	int x;
	int y;
	
	Point()
	{}
	Point(int a, int b)
	{
		this.x = a;
		this.y = b;
	}
}

class LineEq
{
	//         ax + by + c = 0
	int a;
	int b;
	int c;
	
	LineEq()
	{}
	LineEq(int a, int b, int c)
	{
		this.a = a;
		this.b = b;
		this.c = c;
	}
}

public class Searching__6
{
	
	static double distance(double X, double Y, Point p)
	{
		//  dist = sqrt(   (x2-x1)^2   +  (y2-y1)^2   )
		double term1 = (X - p.x) * (X - p.x);
		double term2 = (Y - p.y) * (Y - p.y);
		
		double dist = Math.sqrt(term1 + term2);
		return dist;
	}
	
	static double totalDistance( LineEq l, Point points[] , double X)
	{
		//we will take a point (x is enough we can calculate y using line equation) on the line
		//and set of points. We will calculate the distance between each point in the set 
		//                                and the point in the line 
		// we will return the sum of distances that we have calculated
		
		// step 1:- calculate y          ax + by + c = 0
		//         y = (-ax - c)/b                    y = -1 (ax + c)/b
		double Y = -1 * (l.a * X   +    l.c) / l.b;
		
		//step 2:- calculate distance between (X, Y)   and each point in Point[] and add it
		double sum = 0;
		for(int i=0; i<points.length; i++)
		{
			//we will use another function to do this job
			sum = sum + distance( X, Y, points[i] );
		}
		
		return sum;
	}
	

	static double optimalLocation(LineEq l, Point points[])
	{
		double low = -1e6;
		double high = 1e6;
		int EPS = (int) (1e-6) + 1;
		
		while(high - low > EPS)
		{
        		//we are doing ternary search which divides the array into 3 parts
        		double mid1, mid2;
        		mid1 = low + (high - low)/3;
        		mid2 = mid1 + (high - low)/3;
        		
        		double dist1 = totalDistance(l, points, mid1);
        		double dist2 = totalDistance(l, points, mid2);
        		
        		if(dist1 < dist2)
        			high = mid2;
        		else
        			low = mid1;
		}
		
		return totalDistance(l, points, (low+high)/2);
	}
	
	
	public static void main(String[] args)
	{
		Point points[] = new Point[5];
		
		points[0] = new Point(-3,-2);
		points[1] = new Point(-1, 0);
		points[2] = new Point(-1, 2);
		points[3] = new Point(1, 2);
		points[4] = new Point(3,4);

		LineEq l = new LineEq(1, -1, -3);
		
		double min_dist = optimalLocation(l, points);
		System.out.println(min_dist);
	}

}

Time complexity :- O()
Space complexity :- O()