2015编程之美（资格赛）--基站选址

2
3 3 4 1
1 2
2 1
2 3
3 2
2 2
4 4 4 2
1 2
2 4
3 1
4 3
1 4
1 3

Case #1: 4
Case #2: 13

    这道题，很不好理解：  刚开始代码思路错了n边.....

4 4 4 2
1 2
2 4
3 1
4 3
1 4
1 3  
可以排除基站的坐标为（2，,3) 所以得到的数据欧几里得的距离为{x1*x1+y1*y1);
对于路程为： 直接坐标之差的绝对值（x+y）;
代码：

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<iostream>
 4 #include<string>
 5 #include<vector>
 6 #include<algorithm>
 7 #include<math.h>
 8 #include<stdio.h>
 9 #include<string.h>
10 #include<stdlib.h>
11 using namespace std;
12 const int inf = 0x3f3f3f3f;
13 struct point {
14     int x, y;
15 
16 };
17 
18 void input(point &max_p, point & min_p, vector<point> & aa, const int num) {
19 
20     point tem = { 0,0 };
21     for (int i = 0; i < num; i++) {
22         scanf("%d %d", &tem.x, &tem.y);
23         max_p.x = max(max_p.x, tem.x);
24         min_p.x = min(min_p.x, tem.x);
25         max_p.y = max(max_p.y, tem.y);
26         min_p.y = min(min_p.y, tem.y);
27         aa.push_back(tem);
28     }
29 }
30 
31 //求距离的平方
32 int dist(const point &aa, const point &bb) {
33 
34     int x = aa.x - bb.x;
35     int y = aa.y - bb.y;
36     return x*x + y*y;
37 }
38 
39 //求距离
40 int  dist_sqrt(const point &aa, const point &bb) {
41 
42     int x = abs(aa.x - bb.x);
43     int y = abs(aa.y - bb.y);
44     return  x+y;
45 }
46 
47 int work(const point &max_p, const point & min_p, const vector<point> & aa, const vector<point> & bb) {
48 
49     int x, y;
50     int res = inf, temp = 0,ttu=inf;
51     for (x = min_p.x; x <= max_p.x; x++) {
52         for (y = min_p.y; y <= max_p.y; y++) {
53             temp = 0;
54             point tt = { x,y };
55             for (int i = 0; i <aa.size(); i++) {
56 
57                     temp +=dist(tt, aa[i]);
58             }
59                 ttu = inf;
60             for (int i = 0; i < bb.size(); i++) {
61             ttu= min(dist_sqrt(tt, bb[i]),ttu);
62             }
63              res = min(res, temp+ttu);
64         }
65     }
66     return res;
67 }
68 
69 int main() {
70 
71     int nn, mm, AA, BB;
72     int _case, cnt = 1;
73     vector<point> aa, bb;
74     scanf("%d", &_case);
75     for (cnt = 1; cnt <= _case; cnt++) {
76 
77        point  max_p = { 0,0 }, min_p = { inf,inf };
78         aa.clear(),bb.clear();
79         scanf("%d %d %d %d", &nn, &mm, &AA, &BB);
80         input(max_p, min_p, aa, AA);
81         input(max_p, min_p, bb, BB);
82         int res = work(max_p, min_p, aa, bb);
83 
84         printf("Case #%d: %d\n", cnt, res);
85     }
86     //cin.get();
87     return 0;
88 }