2014-07-18

UVa 10744 - The Optimal Super-Highway

1. Input
2. Output
3. Sample Input
4. Output for Sample Input
5. Solution

In our real life when we look for help we find that only a few people are willing to help us but when we look for suggestions there are thousands waiting with their bag of suggestions. In the country named Culabura a similar situation is creating a lot of trouble. Culabura is a country containing around 20000 important places and infinite land area. The president of Culabura wants to build a super highway through his country. This super highway can be expressed by a straight line that fulfills the following two properties:
a) It must be parallel to another road that connects the two most important cities (denoted by A and B) of the country.

b) The summation of distances of all-important places from it must be minimum.

The advisers of the king of Culabura are giving random and meaningless suggestions to solve this problem (As always is the case with advisers). Now your job is to find the minimum summation of distance. For example in the above picture you will have to find the minimum possible value of (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8). In other words you will have to place the superhighway in such a place so that (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8) is minimum and you will have print this minimum value. In this problem we will call such minimum value sum_d_min. Your solution must be very efficient. /Looking for an O(n) solution /

Input

The input file contains a single set of input. First line of each input set contains two integers N (0<N<20001) and Q(0<Q<101). Here N is the number of important places and Q is the number of queries. Each of the next N lines contains a pair of integer xi and yi (|xi|, |yi|<=100), where (xi, yi) is the coordinate of the i-th (0<=i<=N-1) important place. Each of the next Q lines contains four integers Ax, Ay, Bx, By, where (Ax, Ay) and (Bx, By) are the coordinates of A and B respectively and the optimal super highway must be parallel to street (or line) AB. You must not consider A and B as part of the N important places. Some important places may be present more than in the list to give them extra importance. You don’t need to worry about that and just consider them as two different places. Also remember that place A and B will always be two different places.

Output

For each query produce one line of output. This line contains the serial of output followed by the value of sum_d_min for that particular query. All the output numbers should be rounded to nearest integer. Look at the output for sample input for details.

Sample Input

6 2
1 1
1 10
20 12
2 4
1 1
2 4
10 10 11 11
2 3 3 4

Output for Sample Input

1 2	Case 1: 15 Case 2: 15

Solution

題目描述：

給平面上 N 個點座標，接著詢問平行兩個點的線中，找到一條當作高速公路，使得每一個點到線上最短距離總和最小。

題目解法：

套用點線距公式，可以發現其符合中位數性質，如果不用中位數的方式，也可以藉由排序後採用 DP 的方式找到一個距離最小的線分布 (線一定會經過其中一個點)。

為了加速，捨棄掉$\frac{|ax + by + c|}{\sqrt{a^{2}+b^{2}}}$ 的分母部分，留到最後再除即可。

如果只求中位數，可以針對 Selection Algorithm，在 O(n) 時間內找到，速度快於排序的 O(n log n)

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double distProjection(Pt as, Pt at, Pt s, double &div) {
    long long a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    div = a * a + b * b;
    return (a * s.x + b * s.y + c) /* / hypot(a, b) */;
}
int main() {
    int cases = 0, n, q;
    Pt D[32767], a, b;
    while(scanf("%d %d", &n, &q) == 2) {
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &D[i].x, &D[i].y);
        }
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &a.x, &a.y);
            scanf("%d %d", &b.x, &b.y);
            
            vector<double> dist;
            double div;
            for(int j = 0; j < n; j++)
                dist.push_back(distProjection(a, b, D[j], div));
            sort(dist.begin(), dist.end());
            
            double sum = 0, ret;
            for(int j = 0; j < n; j++)
                sum += dist[j] - dist[0];
            ret = sum;
            for(int j = 1; j < n; j++) {
                sum = sum - (dist[j] - dist[j-1]) * (n - j) + (dist[j] - dist[j-1]) * j;
                ret = min(ret, sum);
            }
            printf("Case %d: %.0lf\n", ++cases, ret / sqrt(div));
        }
    }
    return 0;
}

Morris' Blog