2014
11-30

# Fire station

A city’s map can be seen as a two dimensional plane. There are N houses in the city and these houses can be seen as N points P1 …… PN on the two dimensional plane. For simplicity’s sake, assume that the time spent from one house number to another is equal to the distance between two points corresponding to the house numbers. The government decides to build M fire stations from N houses. (If a station is build in Pi, We can think the station is next to the house and the time from the station to the house is considered zero.) It is obvious that if some place such as Pi is breaking out of fire, the nearest station will dispatched a fire engine quickly rushed to the rescue scene. The time it takes from this station to the rescue scene is called rescue time. Now you need to consider about a problem that how to choice the positions of the M fire station to minimize the max rescue time of all the houses.

The fi rst line of the input contains one integer T, where T is the number of cases. For each case, the fi rst line of each case contains two integers N and M separated by spaces (1 ≤ M ≤N ≤ 50), where N is the number of houses and M is the number of fire stations. Then N lines is following. The ith line contains two integers Xi and Yi (0 ≤ Xi, Yi ≤ 10000), which stands for the coordinate of the ith house.

The fi rst line of the input contains one integer T, where T is the number of cases. For each case, the fi rst line of each case contains two integers N and M separated by spaces (1 ≤ M ≤N ≤ 50), where N is the number of houses and M is the number of fire stations. Then N lines is following. The ith line contains two integers Xi and Yi (0 ≤ Xi, Yi ≤ 10000), which stands for the coordinate of the ith house.

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

1.000000
2.236068

< [if gte mso 9]>

Normal
0

7.8 磅
0
2

false
false
false

MicrosoftInternetExplorer4

< [if gte mso 9]>

< [if gte mso 10]>
<
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
>
< [endif]>

hdu 2295

DLX

/*
Author	: qlyzpqz
Date	: 2010-10-3
Statue	: 3027980	2010-10-03 10:46:28	Accepted	3656	3062MS	304K	2802 B	C++	流水
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 55;
const int MAXL = MAXN * MAXN;
struct Point {
int x, y;
}house[MAXN];
int N, M, num, U[MAXL], D[MAXL], L[MAXL], R[MAXL], head, S[MAXN], col[MAXL], cnt;
double d[MAXN][MAXN], dl[MAXL];
double dist (Point a, Point b) {
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init (int c) {
memset(S, 0, sizeof(S));
for (int i = 0; i <= c; ++i) {
U[i] = D[i] = i;
L[i] = i - 1;
R[i] = i + 1;
col[i] = i;
}
L[0] = c;
R[c] = 0;
cnt = c + 1;
}
void build (double rd) {
int lid, rid;
for (int i = 1; i <= N; ++i) {
lid = rid = cnt;
for (int j = 1; j <= N; ++j) {
if (d[i][j] <= rd) {
U[cnt] = U[j];
D[cnt] = j;
L[cnt] = rid;
R[cnt] = lid;
D[U[j]] = cnt;
U[j] = cnt;
L[lid] = cnt;
R[rid] = cnt;
col[cnt] = j;
S[j]++;
rid = cnt++;
}
}
}
}
void remove (int id) {
for (int i = D[id]; i != id; i = D[i]) {
R[L[i]] = R[i];
L[R[i]] = L[i];
S[col[i]]--;
}
}
void resume (int id) {
for (int i = U[id]; i != id; i = U[i]) {
R[L[i]] = i;
L[R[i]] = i;
S[col[i]]++;
}
}
bool hash[MAXN];
int price () {
int ret = 0;
memset(hash, 0, sizeof(hash));
for (int i = R[head]; i != head; i = R[i]) if (!hash[col[i]]) {
ret++;
hash[col[i]] = 1;
for (int j = D[i]; j != i; j = D[j]) {
for (int k = R[j]; k != j; k = R[k]) {
hash[col[k]] = 1;
}
}
}
return ret;
}
bool dfs (int step) {
if (step + price() > M) return false;
int max = MAXN, id;
for (int i = R[head]; i != head; i = R[i]) {
if (S[i] < max) {
max = S[i];
id = i;
}
}
for (int i = D[id]; i != id; i = D[i]) {
remove(i);
for (int j = R[i]; j != i; j = R[j]) {
remove(j);
}
if (dfs(step + 1)) {
return true;
}
for (int j = L[i]; j != i; j = L[j]) {
resume(j);
}
resume(i);
}
return false;
}
void solve () {
int mid, low, hight;
low = 0;
hight = num - 1;
while (low < hight) {
mid = (low + hight) >> 1;
init(N);
build(dl[mid]);
if (dfs(0)) {
hight = mid;
}
else {
low = mid + 1;
}
}
printf("%.6lf/n", dl[low]);
}
int main () {
freopen("input.txt", "r", stdin);
int kase;
scanf("%d", &kase);
while (kase--) {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
scanf("%d%d", &house[i].x, &house[i].y);
}
num = 0;
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; ++j) {
d[i][j] = d[j][i] = dl[num++] = dist(house[i], house[j]);
}
}
sort(dl, dl + num);
num = unique_copy(dl, dl + num, dl) - dl;
solve();
}
return 0;
}



1. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

2. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

3. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

4. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

5. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

6. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

7. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

8. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

9. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

10. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

11. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

12. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

13. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

14. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

15. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

16. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

17. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

18. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

19. 首先，人家从头到尾只是说35格斗不行，没说别的不行，而格斗能力，其实根本不用黑，推重比和翼载摆在那里，啥黑科技都救不了，其次，你说的前半球通杀，任何飞机装备头盔瞄准具和超级响尾蛇都能做到，作为一个平台而言，35不存在优势，还有就是文中并没有说头盔重，而是

20. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。