yukicoder 202 1円玉投げ

2015/05/15 (Fri) yukicoder 平方分割

問題

問題文

方針

平面を $1$ 辺が $l$ の正方形のバケットで分割し， 当たり判定は注目するコインが属するバケットとその近傍の $9$ 個のみで行う． 典型何で良い問題だなあと思った．

コンテスト中はテストケースがファイル名から読み取れたので手抜きしていたが， 後日落とされてしまった． ところで，yukicoder の嘘解法は徹底的に落とす方針自体は良いと思うが， 落とされるとシステム上コンテストに参加すらしていないことになるのはどうなんだろう．

実装

int N;
int const l = 50;
vector<pair<int,int>> baq[200010/l][200010/l];

bool check(int x, int y){
    int bx = x/l, by = y/l;
    for(int i=by-1;i<=by+1;i++){
        for(int j=bx-1;j<=bx+1;j++){
            for(auto & p : baq[i][j]){
                int cx, cy;
                tie(cx,cy) = p;
                int dx = x-cx, dy = y-cy;
                int d2 = dx*dx + dy*dy;
                if(d2 < 400) return false;
            }
        }
    }
    return true;
}

int main(){
    cin >> N;
    int ans = 0;
    rep(i,N){
        int x,y;
        cin >> x >> y;
        x += l;
        y += l;
        if(!check(x,y)) continue;
        baq[y/l][x/l].eb(x,y);
        ans++;
    }
    cout << ans << endl;
}