Gathering

Introduction

This problem asks to find the point with the minimum total manhattan distance to all given points (10^5) while also being at most D (10^9)away from all points.

Solutions

Valid Points

Idea

1. Find the range of points that are within D of all other points
2. Find the range of points that are at minimum total distance to all other points
3. The solutions is either on the boundary from part 1, or the range in part 2 is enclosed with the range in part 1, in which case any point from part 1 is valid

Calculating valid points

The points manhattan distance D from a point form a rectangle with diagonal of 2*D (aka a square). The intersection of two such diamonds is another rectangle, and can be found trivially by finding the two intersecting lines from each rectangle (2 points) and then taking the corner point from each rectangle which is contained within the other. This is done iteratively until rectangles are intersected.

Coordinate transformation

Though not required, the coordinate system can be rotated 45 degrees to yield horizontal rectangles rather than diagonal ones, which are much easier to intersect (Since you can use min and max). The transformation is:

rectangular to diagonal: x' = y + x y' = y - x

diagonal to rectangular: x = (x' - y') / 2 y = (x' + y') / 2

Note that distances are distorted during the transform, so you must transform back before calculating any manhattan distances

BONUS: java users can use the rectangle2D.double class, which has a "createIntersection" method that does all the work for you (as well as a "contains" method...useful later)

Calculating the minimum total distance points

Since we're using manhattan distance, the distance in the x and y dimensions are independent. Therefore we simply calculate the minimum value in the x dimension, and then in the y dimension, and then have our range. In a single dimension, we know the minimum must have an equal number of points on either side (Proof: assume an optimal solution has more points on one side. Take one step towards the side with more points, and your total distance to all points will decrease. QED). The place with the same number of points on either side is the median. If there are an odd number of points, it's a single point at the middle x and y coordinates. If it's an even number, it's the range between the two middle most x and y coordinates.

Combining the two ranges

If the valid range contains the median, then we're done (here's where the contains method comes in handy). If not, then the solution will be some point on the boundary (on the side facing the median). Ternary search across the side of the boundary of valid points facing the median to find the minimum. Finding the right edge can be a pain though, so just run ternary search across all four edges and take the minimum of all of them.

Gotchas

• The bounds of the box from part 1 may not have integral vertices. Either maintain the decimal value and worry about integral later, or ensure you grab the correct integral values now
• When the box from part one does NOT contain the median, the solution may not fall at a corner.
• The box from part 1 might have 0 height or width...and may just be a single point
• There are a a ton of corner cases in ternary search where you can get stuck. It's easier to just use the decimal values until the bounds are close and then take the best of the 4 surrounding integral points.

Runtime

• 100,000 * log(10^9) * 4 = 10 million or so

Code

Solution - Java

import java.util.*;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.geom.Rectangle2D.Double;
public class g {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new g().go();
	}
	private void go() {
		int n=in.nextInt();
		long[][] p=new long[n][2];
		ArrayList<Long> x=new ArrayList<Long>(),y=new ArrayList<Long>();
		for(int i=0;i<n;i++){
			p[i][0]=in.nextInt();
			p[i][1]=in.nextInt();
			x.add(p[i][0]);
			y.add(p[i][1]);
		}
		long d=in.nextInt();
		Collections.sort(x);
		Collections.sort(y);
		Point2D.Double bot=new Point2D.Double(p[0][0],p[0][1]-d);//compute valid box in rectangular points (cuz it's easy in java)
		Rectangle2D.Double r=new Rectangle2D.Double(bot.y+bot.x,bot.y-bot.x,2*d,2*d);
		for(int i=1;i<n;i++){
			bot=new Point2D.Double(p[i][0],p[i][1]-d);
			r=(Double) r.createIntersection(new Rectangle2D.Double(bot.y+bot.x,bot.y-bot.x,2*d,2*d));
		}
		if(r.getHeight()<0 || r.getWidth()<0){
			System.out.println("impossible");
			System.exit(0);
		}
		if(x.size()%2==0){//min lies on box boundary unless box wholly contains the median
			long xl=x.get(n/2-1),xh=x.get(n/2),yl=y.get(n/2-1),yh=y.get(n/2);
			if(r.contains(yl+xl,yl-xl)&&r.contains(yl+xh,yl-xh)&&r.contains(yh+xl,yh-xl)&&r.contains(yh+xh,yh-xh)){
				System.out.println(tot(xl,yl,p,d));
				System.exit(0);
			}
		} else {
			long xx=x.get(n/2),yy=y.get(n/2);
			if(r.contains(yy+xx,yy-xx)){
				System.out.println(tot(xx,yy,p,d));
				System.exit(0);
			}
		}//at least some part of the median is outside the box, min is along one of the edges
		long min=Long.MAX_VALUE;
		double[][] bs=new double[4][2];
		bs[0][0]=r.getMinX()-r.getMinY();
		bs[0][1]=r.getMinX()+r.getMinY();
		bs[1][0]=r.getMaxX()-r.getMinY();
		bs[1][1]=r.getMaxX()+r.getMinY();
		bs[2][0]=r.getMaxX()-r.getMaxY();
		bs[2][1]=r.getMaxX()+r.getMaxY();
		bs[3][0]=r.getMinX()-r.getMaxY();
		bs[3][1]=r.getMinX()+r.getMaxY();
		for(int i=0;i<4;i++)for(int j=0;j<2;j++)bs[i][j]/=2;//convert back to diagonal coordinates before ternary searching
		for(int i=0;i<4;i++){
			min=Math.min(min,tern(bs[i][0],bs[i][1],bs[(i+1)%4][0],bs[(i+1)%4][1],p,d));
		}
		System.out.println(min);
	}
	private long tern(double d, double e, double f, double g,long[][] p,long dd) {//min of ternary search over the edge
		while(Math.abs(f-d)>.1||Math.abs(g-e)>.1){
			double h=d+(f-d)/3,i=e+(g-e)/3,j=d+2*(f-d)/3,k=e+2*(g-e)/3;
			if(tot(h,i,p,dd)<tot(j,k,p,dd)){
				f=j;
				g=k;
			} else {
				d=h;
				e=i;
			}
		}//Next line guarantees we have an integral value...since easier to ternary search with float values
		return Math.min(tot(Math.floor(d),Math.floor(e),p,dd),Math.min(tot(Math.floor(d),Math.ceil(e),p,dd), Math.min(tot(Math.ceil(d),Math.floor(e),p,dd),tot(Math.ceil(d),Math.ceil(e),p,dd))));
	}
	private long tot(double x,double y,long[][] p,long d) {
		long out=0;
		for(int i=0;i<p.length;i++){
			long temp=(long) (Math.abs(x-p[i][0])+Math.abs(y-p[i][1]));
			if(temp>d)return Long.MAX_VALUE;
			out+=temp;
		}
		return out;
	}
}