2015编程之美资格赛题目3 : 基站选址 分类： 算法

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个点的距离最小。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MOD 100007
using namespace std;

int m , n , num_a,num_b, x, y;
int x1[1001], y1[1001], x2[1001], y2[1001]; 
long long sum_x, sum_y, ans ,ans_x, ans_y;

void find_ans(int x, int y) {
	int s = 0, temp = INT_MAX;

	for (int k = 1; k <= num_1; k++)
		s += (x1[k] - x) * 1LL * (x1[k] - x) + (y1[k] - y) * 1ll * (y1[k] - y);
	for (int k = 1 ; k <= num_b; k++)
		temp = min(temp, abs(x2[k]-x) + abs(y2[k]-y)*1LL);
	if(s+temp = 1 && i <= n && j >=1 && j <=m)
					find_ans(i,j);
			}
        printf("Case #%d: %d\n",num,ans);
    }
    return 0;
}