uva 1325 - Hypertransmission(暴力枚举）

题目链接：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;
}

uva 1325 - Hypertransmission(暴力枚举）

原文：http://blog.csdn.net/keshuai19940722/article/details/19283879