Problem Solve: CodeChef DEC09 Plant Location

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.

This is maybe the easiest problem in the contest. A total of 95 contestants solved the problem correctly.

My Solution

Let f(x) be the sum of the points’ distances from point P when P is located on the straight line and has X-coordinate of x. After a little time thinking, I realized that the graph of f(x) with respect to x is like the quadratic function graph. That is, f(x) is first strictly decreasing (from negative infinity to the leftmost point) and then strictly increasing (from the rightmost point to positive infinity). The turning point is the value we are looking for.

That property of function f(x) allows us to perform a ternary search on x.

My code follows.

#include <cstdio>
#include <cmath>
int T, N, A, B, C, X[2000], Y[2000];

double f(double x)
{
    double y = (-C - A*x)/(1.*B);
    double res = 0;
    for (int i = 0; i < N; i++)
        res += hypot(X[i]-x, Y[i]-y);
    return res;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &N);
        scanf("%d%d%d", &A, &B, &C);
        for (int i = 0; i < N; i++)
            scanf("%d%d", &X[i], &Y[i]);
        double lo = -50000, hi = 50000;
        while (hi-lo > 1e-7)
        {
            double l = (lo*2+hi)/3, r = (lo+hi*2)/3;
            if (f(l) > f(r))
                lo = l;
            else
                hi = r;
        }
        printf("%.6lf\n", f(lo));
    }
}

Enjoyed this article? Subscribe to our RSS feed for free!

Be the first to comment!