题目链接:uva 1325 - Hypertransmission
题目大意:有n个星球,每个星球有坐标xyz,以及自己的频道,1或0,现在要求一个收听半径R,使得尽量多的星球是间谍星球,并且半径尽量小,间谍星球的标准是收听不同类的频道不小于同类频道,注意,星球可以收听自己的频道。
解题思路:首先计算出两两星球之间的距离,按照从小到大排序,然后以星球的距离作为半径进行枚举,为或最大值,注意如果全是同类频道的情况,R为0.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1005;
struct Point {
double x, y, z;
int sign, same, diff;
}p[N];
struct Dist {
int l, r;
double len;
}d[N*N];
int n, c;
double handle(double xi, double yi, double zi) {
return sqrt(xi*xi + yi*yi + zi*zi);
}
bool cmp(const Dist& a, const Dist& b) {
return a.len < b.len;
}
void init () {
c = 0;
for (int i = 0; i < n; i++) {
scanf("%lf%lf%lf%d", &p[i].x, &p[i].y, &p[i].z, &p[i].sign);
p[i].same = 1; p[i].diff = 0;
for (int j = 0; j < i; j++) {
d[c].l = i; d[c].r = j;
d[c++].len = handle(p[i].x - p[j].x, p[i].y - p[j].y, p[i].z - p[j].z);
}
}
sort(d, d + c, cmp);
}
void solve () {
int ans = 0, tmp = 0;
double R = 0;
for (int i = 0; i < c; i++) {
int t = d[i].l, k = d[i].r;
if (p[t].sign == p[k].sign) {
if (p[t].diff - p[t].same == 1) tmp--;
if (p[k].diff - p[k].same == 1) tmp--;
p[t].same++; p[k].same++;
} else {
if (p[t].same == p[t].diff) tmp++;
if (p[k].same == p[k].diff) tmp++;
p[t].diff++; p[k].diff++;
}
if (i != c - 1 && fabs(d[i].len - d[i+1].len) < 1e-9) continue;
if (tmp > ans) {
ans = tmp; R = d[i].len;
}
}
printf("%d\n%.4lf\n", ans, R);
}
int main () {
while (scanf("%d", &n) == 1) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC