算法设计第三次上机作业-Raid
题目描述
有两种类型的点，一种是station，一种是agent，计算station和agent的最小距离。
输入 第一行是T，代表样例个数 之后的每一种情况，第一行是N，代表有N个station和N个agent。 接下来的2N行，依次是station和agent的坐标。
输出 每一行都输出最小距离，保留到小数点后三位。
解题思路
和求取平面内最小距离点对的解法一样，只不过这里给每个点增加一个标签，在比较和计算最小距离的时候仅计算不同标签的点对。 分治法求取最小点对的方法是这样的：
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define Max 20005
const double Max_Value
=1e100;
using namespace std
;
struct node
{
double x
, y
;
int type
;
};
int cmpy(node node1
, node node2
) {
return node1
.y
<node2
.y
;
}
int cmpx(node node1
, node node2
) {
return node1
.x
<node2
.x
;
}
double cal_dis(node a
, node b
) {
return sqrt((a
.x
-b
.x
)*(a
.x
-b
.x
)+(a
.y
-b
.y
)*(a
.y
-b
.y
));
}
double closest_pair(node nodes
[], int left
, int right
) {
if(left
>= right
) return Max_Value
;
if(right
- left
== 1) {
if((nodes
[right
].type
^nodes
[left
].type
) == 1) {
return cal_dis(nodes
[right
], nodes
[left
]);
}
else return Max_Value
;
}
int mid
= (left
+right
)/2;
double left_min
= closest_pair(nodes
, left
, mid
);
double right_min
= closest_pair(nodes
, mid
+1, right
);
double min_value
;
min_value
= min(left_min
, right_min
);
vector
<node
> nodes_line
;
for(int i
=left
; i
<=right
; i
++) {
if(fabs(nodes
[i
].x
-nodes
[mid
].x
) <= min_value
) {
nodes_line
.push_back(nodes
[i
]);
}
}
sort(nodes_line
.begin(), nodes_line
.end(), cmpy
);
for(int i
=0; i
<nodes_line
.size(); i
++) {
double temp
= 0;
for(int j
=i
+1; j
<nodes_line
.size(); j
++) {
temp
= cal_dis(nodes_line
[j
], nodes_line
[i
]);
if(temp
< min_value
&& (nodes_line
[i
].type
^nodes_line
[j
].type
)==1) {
min_value
= temp
;
}
}
}
return min_value
;
}
int main(int argc
, const char * argv
[]) {
int n
, t
;
node nodes
[Max
];
cin
>>t
;
for(int j
=0; j
<t
; j
++) {
cin
>>n
;
for(int i
=0; i
<2*n
; i
++) {
scanf("%lf%lf", &nodes
[i
].x
, &nodes
[i
].y
);
if(i
<n
) {
nodes
[i
].type
= 0;
}
else {
nodes
[i
].type
= 1;
}
}
sort(nodes
, nodes
+2*n
, cmpx
);
double result
= closest_pair(nodes
, 0, 2*n
-1);
printf("%.3lf\n",result
);
}
return 0;
}
