rambo

基站选址

2015年4月20日 ACM解题 0 Comments

 

描述

需要在一个N × M的网格中建立一个通讯基站，通讯基站仅必须建立在格点上。网格中有A个用户，每个用户的通讯代价是用户到基站欧几里得距离的平方。网格中还有B个通讯公 司，维护基站的代价是基站到最近的一个通讯公司的路程（路程定义为曼哈顿距离）。在网格中建立基站的总代价是用户通讯代价的总和加上维护基站的代价，最小 总代价。

输入

第一行为一个整数T，表示数据组数。每组数据第一行为四个整数：N, M, A, B。接下来的A+B行每行两个整数x, y，代表一个坐标，前A行表示各用户的坐标，后B行表示各通讯公司的坐标。

输出

对于每组数据输出一行"Case #X: Y"，X代表数据编号（从1开始），Y代表所求最小代价。

数据范围

1 ≤ T ≤ 20 , 1 ≤ x ≤ N,1 ≤ y ≤ M, 1 ≤ B ≤ 100

小数据 1 ≤ N, M ≤ 100, 1 ≤ A ≤ 100

大数据 1 ≤ N, M ≤ 107   1 ≤ A ≤ 1000

解题思路：题目中的距离分别为1范数和2范数的平方，所以这里我们首先应该考虑用户的通讯代价，这个是主要因素。可以知道当选取用户坐标的几何中心，并以该中心搜索其邻域（3×3）的邻域，当基站选址落入这个邻域时，显然其到各个用户的通讯代价应为最小，同时计算该基站到通讯公司的曼哈顿距离，即为最终的最小代价。这道题目运用了先验知识。

代码参考http://hihocoder.com/contest/msbop2015qual/solution/325370

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
#define mxn 200005
#define LL long long
#define MP make_pair
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
 
int dx[] = {0, 0, 0, 1, 1, 1, -1, -1, -1};
int dy[] = {0, 1, -1, 0, 1, -1, 0, 1, -1};
 
LL ABS(LL x) {
    return x < 0 ? -x : x;
}
 
struct point {
    LL x, y;
    point(){};
    point(LL x, LL y):x(x),y(y){}
    point operator - (const point& b) const {
        return point(x - b.x, y - b.y);
    }
    void input() {
        cin >> x >> y;
    }
    LL dis() {
        return x * x + y * y;
    }
    LL len() {
        return ABS(x) + ABS(y);
    }
}A[1005], B[105];
 
LL cal(point o, int a, int b) {
    LL ret = ~0uLL >> 1;
    REP(i, 1, b) ret = min(ret, (o - B[i]).len());
    REP(i, 1, a) ret += (o - A[i]).dis();
    return ret;
}
 
int main()
{
    int t, n, m, a, b, cas = 0;
 
    cin >> t;
    while (t--) {
        cin >> n >> m >> a >> b;
        REP(i, 1, a) A[i].input();
        REP(i, 1, b) B[i].input();
        LL ans = ~0uLL >> 1, x = 0, y = 0;
        REP(i, 1, a) x += A[i].x, y += A[i].y;
        x /= a, y /= a;
        FOR(k, 0, 9) {
            LL tx = x + dx[k], ty = y + dy[k];
            if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
            ans = min(ans, cal(point(tx, ty), a, b));
        }
        cout << "Case #" << ++cas << ": " << ans << endl;
    }
    return 0;
}