?? 2063.cpp
字號:
/* 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -