UVa 1325 - Hypertransmission

链接

传送门

题意

给出$n$个星球的位置和广播的类型,定义接受与自身不同类型的个数大于相同类型个数的星球为间谍星球(星球自身的广播也算在内),输出使间谍星球个数的最大值,和最大值下的接受半径。

思路

枚举所有星球间的边,从小到大排序,依次将边加入。注意加边时要将同长度的边一起加入。

代码

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
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const int maxn = 1010;
struct point {
double x, y, z;
int type, same, diff;
} p[maxn];
struct node {
int u, v;
double l;
bool operator < (const node& rhs) const {
return l < rhs.l;
}
} d[maxn * maxn];
double dis(point& a, point& b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
int main() {
int n;
while (~scanf("%d", &n)) {
for (int i = 0; i < n; ++i) {
p[i].diff = 0, p[i].same = 1;
scanf("%lf%lf%lf%d", &p[i].x, &p[i].y, &p[i].z, &p[i].type);
}
int num = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
d[num].u = i, d[num].v = j;
d[num].l = dis(p[i], p[j]);
++num;
}
}
sort(d, d + num);
int ans = 0, res = 0;
double r = 0;
for (int i = 0; i < num; ++i) {
point& a = p[d[i].u];
point& b = p[d[i].v];
if (a.type == b.type) {
if (a.same + 1 == a.diff) {
--res;
}
if (b.same + 1 == b.diff) {
--res;
}
++a.same, ++b.same;
} else {
if (a.same == a.diff) {
++res;
}
if (b.same == b.diff) {
++res;
}
++a.diff, ++b.diff;
}
if (i != num - 1 && fabs(d[i].l - d[i + 1].l) < eps) {
continue;
}
if (res > ans) {
ans = res;
r = d[i].l;
}
}
printf("%d\n%.4lf\n", ans, r);
}
return 0;
}