Given list of 2d points, find the point closest to all other points

Lets analysis this problem. We need to find the point closest to all other points in a 2d plane. What if it is only 1d plane? The point is the median.

What about 2d plane, we can first map all the points to the x axis and sort the points and thus forms a 1d array. Then we can calculate the sum of distance to all the other points for each point (by scanning the array from left to right then right to left). Then we do the same on y axis. The distance between two points is x^2 + y^2 and because x and y are all distance, which means x and y are all >= 1, so if x1 + y1 >= x2 + y2 => x1^2 + y1^2 >= x2^2 + y2^2.

 

 

class Point {
	int x, y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	@Override 
	public boolean equals(Object obj) {
		if (!obj instance of Point) {
			return false;
		}
		return (obj.x == this.x && obj.y == this.y);
	}
	
	@Override 
	public int hashCode () {
		return 31*x + y;
	}
}

class solution {
	public Point findMin(Point[] p) {
		HashMap<Point, Integer> map = new HashMap<Point, Integer>();
		for (int i = 0; i < p.length; i++) {
			map.add(p[i], 0);
		}
		Arrays.sort(p, new Comparator<Point>() {
			@Override
			public int compare(Point p1, Point p2) {
				if (p1.x > p2.x)
					return 1;
				if (p1.x < p2.x)
					return -1;
				return 0;
			}
		});
		int [] disX = new int [p.length];
		//find distance from the left
		disX[0] = 0;
		for (int i = 1; i < disX.length; i++) {
			disX[i] = i*(p[i] - p[i-1]) + disX[i-1];
		}
		//find distance from the right
		int [] tmpX = new int [p.length];
		tmpX[p.length - 1] = 0;
		for (int i = tmpX.length - 2; i >= 0; i--) {
			tmpX[i] = (p.length - i)*(p[i]-p[i+1]) + tmpX[i+1];
			disX[i] += tmpX[i];
			map.put(p[i], disX[i]);
		}
		
		//do the same for y
		Arrays.sort(p, new Comparator<Point>() {
			@Override
			public int compare(Point p1, Point p2) {
				if (p1.y > p2.y)
					return 1;
				if (p1.y < p2.y)
					return -1;
				return 0;
			}
		});
		int [] disY = new int [p.length];
		//find distance from the left
		disY[0] = 0;
		for (int i = 1; i < disY.length; i++) {
			disY[i] = i*(p[i] - p[i-1]) + disY[i-1];
		}
		//find distance from the right
		int [] tmpY = new int [p.length];
		tmpY[p.length - 1] = 0;
		for (int i = tmpY.length - 2; i >= 0; i--) {
			tmpY[i] = (p.length - i)*(p[i]-p[i+1]) + tmpY[i+1];
			disY[i] += tmpY[i];
			map.put(p[i], map.get(p[i]) + disY[i]);
		}
		//calculate the 2d distance by adding x and y
		Point min = p[0];
		int minDis = map.get(p[0]);
		for (int i = 1; i < p.length; i++) {
			if (map.get(p[i]) < minDis) {
				minDis = map.get(p[i]);
				min = p[i];
			}
		}
		return min;
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s