2063.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2063 on 2006-03-11 at 19:29:06 */ 
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;

const int CR = 250;
const int MAX = 320;
const double eps = 1e-5;

double cx[2], cy[2];

class Unit {
public:
	int x, y, p;
	Unit(int tx = 0, int ty = 0) : x(tx), y(ty) {}
	void make();
	bool operator <(const Unit&) const;
	bool edge(const Unit&) const;
};
void Unit::make() {
	scanf("%d %d %d", &x, &y, &p);
}
bool Unit::operator <(const Unit& u) const {
	if(x != u.x) return x < u.x;
	else return y < u.y;
}
bool Unit::edge(const Unit& u) const {
	int d = (x-u.x) * (x-u.x) + (y-u.y) * (y-u.y);
	if(d > 4*CR*CR) return false;
	double ed = sqrt(1.0*d), dr = sqrt(1.0*CR*CR-0.25*d);
	double dx = dr*(y-u.y)/ed, dy = dr*(x-u.x)/ed, mx = 0.5*(x+u.x), my = 0.5*(y+u.y);
	cx[0] = mx+dx; cy[0] = my-dy; cx[1] = mx-dx; cy[1] = my+dy;
	return true;
}

int main()
{
	int t, i, j, k, o, n;
	Unit u[MAX];
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		int best = 0;
		for(i = 0; i < n; i++) { u[i].make(); best = max(best, u[i].p); }
		sort(u, u+n);
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++) {
				if(!u[i].edge(u[j])) continue;
				for(o = 0; o < 2; o++) {
					int b = lower_bound(u, u+n, Unit((int)cx[o]-CR, -1<<30)) - u;
					int affect = 0, lmt = (int)cx[o]+CR+1;
					for(k = b; k < n && u[k].x <= lmt; k++)
						if((cx[o]-u[k].x)*(cx[o]-u[k].x)+(cy[o]-u[k].y)*(cy[o]-u[k].y)-CR*CR < eps) affect += u[k].p;
					best = max(best, affect);
				}
			}
		printf("Data set #%d:\nThe maximum affected Power Point is %d.\n\n", t, best);
	}
	
	return 0;
}