This is a write-up for the problem Plant Location in CodeChef December 2009 Challenge.

Problem Statement

Given N points (x, y) on a plane and a straight line (Ax+By+C = 0), determine the position of point P on the line such that the sum of all points’ distances from point P is minimum.

Constraints

• 1 ≤ N ≤ 2000.
• |A|, |B|, |C| ≤ 5000; B ≠ 0.
• |x|, |y| ≤ 5000.
• No points lie on the straight line.
• No points share the same positions.
• A, B, C, x, y are integers.
• Time limit is 3 seconds.

Click to read more….