結果

問題 No.202 1円玉投げ
ユーザー たこし
提出日時 2015-06-08 16:24:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
コンパイル時間 1,032 ms
コンパイル使用メモリ 93,636 KB
実行使用メモリ 813,312 KB
最終ジャッジ日時 2024-12-22 09:29:16
合計ジャッジ時間 31,899 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 14 MLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-10
#define PI acos(-1)
#define LL long long

using namespace std;

#define MAX_X 20001
#define MAX_Y 20001
#define MAX_N 100001

int N;
int _N;

bool Filed[MAX_Y][1 << 16];

void init(){

  _N = 1;
  while(_N < MAX_X)
    _N *= 2;

  _N--;

}

void add(int x, int y){

  x += _N;
  
  while(true){
    Filed[y][x] = true;
    if(x == 0)
      break;
    x = (x-1)/2;
  }

}

//y座標の[a,b)の中に円があるかどうか
//外から呼ぶときはquey(y,a,b,0,0,MAX_X)
bool query(int y, int a, int b, int k, int l, int r){
  
  if(b <= l || r <= a)
    return false;

  if(a <= l && r <= b)
    return Filed[y][k];

  bool left, right;
  left = query(y, a, b, k*2+1, l, (r+l)/2);
  right = query(y, a, b, k*2+2, (r+l)/2, r);

  return left || right;

}

int main(){

  cin >> N;
  init();

  int ans = 0;
  
  for(int i = 0; i < N; i++){
    int X, Y;
    cin >> X >> Y;
    int upY = min(MAX_Y-1, 20+Y);
    int downY = max(0, Y-20);
    bool flag = false;
    for(int j = downY; j <= upY; j++){
      int lx = max(0, X - (int)sqrt(400 - pow(j-Y, 2) - 1));
      int rx = min(MAX_X-1,X + (int)sqrt(400 - pow(j-Y, 2) - 1));
      //cout << X << " " << Y << " " << j << " " << lx << " " << rx << endl;
      bool tmp = query(j, lx, rx+1, 0, 0, _N);
      if(tmp){
	//cout << i << " " << j << endl;
	flag |= tmp;
	break;
      }
    }
    if(!flag){
      ans++;
      add(X, Y);
    }
  }

  cout << ans << endl;

  return 0;

}
0