No.202 1円玉投げ - yukicoder
- バケット法を使う。分割領域に含まれる一円玉の最大個数はたかだか 25 個程度なので十分間に合う。
class ThrowOneYenCoin {
public:
static const int r = 10;
typedef pair<int,int> Pt;
bool hit(const Pt &a, const Pt &b) {
int ax,ay,bx,by;
tie(ax,ay) = a;
tie(bx,by) = b;
return (ax-bx)*(ax-bx)+(ay-by)*(ay-by) < 4*r*r;
}
void solve(void) {
int N;
cin>>N;
const int B = 100;
const int maxX = 20000;
const int maxY = 20000;
const int maxBX = maxX/B;
const int maxBY = maxY/B;
list<Pt> field[maxBY+1][maxBX+1];
REP(i,N)
{
int x,y;
cin>>x>>y;
Pt p(x,y);
int bx = x/B;
int by = y/B;
int dx[] = {-1,0,1};
int dy[] = {-1,0,1};
bool ok = true;
REP(j,3)
REP(k,3)
{
int nx = bx+dx[j];
int ny = by+dy[k];
if (nx < 0 || ny < 0 || maxBX < nx || maxBY < ny)
continue;
auto &f = field[ny][nx];
for (auto c : f)
{
if ( hit(c,p) )
ok = false;
}
}
if (ok)
field[by][bx].push_back(p);
}
ll cnt = 0;
REP(i,maxBX+1)
REP(j,maxBY+1)
{
auto &f = field[j][i];
cnt += f.size();
}
cout<<cnt<<endl;
}
};