Yuki 202 1円玉投げ ( Bucket )

題意：
丟半徑 10 的銅板。每次丟完後，若剛好這個硬幣落在另一個已在地上的硬幣，換句話說重疊，就立刻取回這個硬幣，否則留在原地。求最終有多少硬幣在地上。

資料規模：
銅板數 1 ≤ N ≤ 1e5
銅板圓心座標 0 ≤ X[ i ], Y[ i ] ≤ 2e4，整數範圍
時限 5000 ms
記憶體 512 MB

解法：
考慮分塊處理，根據鴿籠原理，每個 10 * 10 的塊必然至多只有一個硬幣。對於任意一個塊裡的硬幣，關心的是以該快為中心的 5 * 5 範圍的塊。

時間 / 空間複雜度：
O( max( X / 10 ) * max( Y / 10 ) )

int N;
vi X, Y;

void init(){
  cin >> N;
  X = Y = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> X[ i ] >> Y[ i ];
}

int cx[ 2000 + 1 ][ 2000 + 1 ];
int cy[ 2000 + 1 ][ 2000 + 1 ];

int eu_dis2( int x, int y, int a, int b ){
  int dtx = x - a;
  int dty = y - b;
  return dtx * dtx + dty * dty;
}

void preprocess(){
  memset( cx, -1, sizeof( cx ) );
  for( int i = 0; i < N; ++i ){
    int x = X[ i ], y = Y[ i ];
    if( cx[ x / 10 ][ y / 10 ] != -1 ) continue;
    int ng = 0;
    for( int dx = -2; dx <= 2; ++dx ){
      for( int dy = -2; dy <= 2; ++dy ){
        int nx = x / 10 + dx;
        int ny = y / 10 + dy;
        if( nx < 0 or nx > 2000 or ny < 0 or ny > 2000 ) continue;
        if( cx[ nx ][ ny ] == -1 ) continue;
        if( eu_dis2( x, y, cx[ nx ][ ny ], cy[ nx ][ ny ] ) >= 400 ) continue;
        ng = 1;
      }
    }
    if( ng ) continue;
    cx[ x / 10 ][ y / 10 ] = x;
    cy[ x / 10 ][ y / 10 ] = y;
  }
}

void solve(){
  int ans = 0;
  for( int i = 0; i <= 2000; ++i )
    for( int j = 0; j <= 2000; ++j )
      ans += cx[ i ][ j ] != -1;
  cout << ans << endl;
}