結果

問題 No.202 1円玉投げ
コンテスト
ユーザー btk
提出日時 2015-05-27 23:00:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 238 ms / 5,000 ms
コード長 4,217 bytes
コンパイル時間 1,251 ms
コンパイル使用メモリ 102,444 KB
実行使用メモリ 19,988 KB
最終ジャッジ日時 2024-12-22 09:22:49
合計ジャッジ時間 6,291 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

struct Point{
	int x, y;
	int id;
};



struct Node{
	Point p;
	Node* left;
	Node* right;
};

typedef vector<Point> VP;
bool LessX(const Point& left, const Point& right){
	if (left.x == right.x)
		return(left.y < right.y);
	else
		return(left.x < right.x);
}

bool LessY(const Point& left, const Point& right){
	if (left.y == right.y)
		return(left.x < right.x);
	else
		return(left.y < right.y);
}


vector<bool> exist(100001, false);
inline int dist(Point& a, Point &b){
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);

}
bool rect_search(Node* root, Point st, Point ed,Point t, bool odd){
	if (root == NULL)return false;
	//if ((st.x <= root->p.x&&root->p.x <= ed.x) && (st.y <= root->p.y&&root->p.y <= ed.y))implements.push_back(root->p);
	if (exist[root->p.id] && dist(root->p, t) < 400)return true;
	if (odd){
		if (ed.y < root->p.y){
			//領域が分割線よりも下側
			if (rect_search(root->left, st, ed, t, odd ^ 1))return true;
		}
		else if (st.y > root->p.y){
			//領域が分割線よりも上側
			if(rect_search(root->right, st, ed, t,odd ^ 1))return true;
		}
		else{
			//領域が分割線にまたがる
			Point mid_l = { ed.x, root->p.y };//分割線の左端
			Point mid_r = { st.x, root->p.y };//分割線の右端
			if(rect_search(root->left, st, mid_l, t,odd ^ 1))return true;
			if(rect_search(root->right, mid_r, ed, t, odd ^ 1))return true;
		}
	}
	else{
		if (ed.x < root->p.x){
			//領域が分割線よりも左側
			if(rect_search(root->left, st, ed, t,odd ^ 1))return true;
		}
		else if (st.x > root->p.x){
			//領域が分割線よりも右側
			if(rect_search(root->right, st, ed, t,odd ^ 1))return true;
		}
		else{
			//領域が分割線にまたがる
			Point mid_l = { root->p.x, ed.y };//分割線の上端
			Point mid_r = { root->p.x, st.y };//分割線の下端
			if(rect_search(root->left, st, mid_l,  t,odd ^ 1))return true;
			if(rect_search(root->right, mid_r, ed, t, odd ^ 1))return true;
		}
	}
	return false;
}


Node* make_Tree(VP::iterator main_s, VP::iterator main_e,
	VP::iterator sub_s, VP::iterator sub_e,
	int size, bool odd){
	if (size <= 0){
		return(NULL);
	}
	Node* n = (Node*)calloc(1, sizeof(Node));
	VP::iterator mid = main_s + size / 2;
	n->p = *mid;
	if (size == 1){
		n->left = NULL;
		n->right = NULL;
	}
	else{
		VP l, r;
		l.reserve(size / 2);
		r.reserve(size - size / 2);

		for (VP::iterator it = sub_s; it != sub_e; ++it)
			//深さが奇数のノードのとき,yで分割
			if ((odd&&LessY(*it, *mid)) || ((!odd) && LessX(*it, *mid)))
				l.push_back(*it);
			else if ((it->x != mid->x) || (it->y != mid->y))
				r.push_back(*it);

		n->left = make_Tree(l.begin(), l.end(), main_s, mid, size / 2, odd ^ 1);
		n->right = make_Tree(r.begin(), r.end(), mid + 1, main_e, size - size / 2 - 1, odd ^ 1);
	}
	return n;
}



void free_Tree(Node* root){
	//printf("Node(%d,%d)\n", root->p.x, root->p.y);
	if (root->left != NULL)
		free_Tree(root->left);
	if (root->right != NULL)
		free_Tree(root->right);
	free(root);
	return;
}

bool operator<(const Point&left, const Point&right){
	if (left.x == right.x)
		return(left.y < right.y);
	else
		return(left.x < right.x);
}
#define all(_b) (_b).begin(),(_b).end()
int main(void){
	int n,res=0;
	cin >> n;
	VP input(n);
	set<Point> memo;
	for (int i = 0; i < n; i++){
		cin >> input[i].x >> input[i].y;
		input[i].id = i;
		if (memo.count(input[i]) == 1){
			i--, n--;
		}
		else memo.insert(input[i]);
	}
	input.resize(n);
	VP x=input,y = input;
	sort(all(x), LessX);
	sort(all(y), LessY);
	Node *root = make_Tree(all(x), all(y), n,false);
	for (int i = 0; i < n; i++){
		Point st, ed;
		st.x = input[i].x - 20;
		st.y = input[i].y - 20;
		ed.x = input[i].x + 20;
		ed.y = input[i].y + 20;
		if (rect_search(root, st, ed, input[i], false)==false){
			exist[i] = true; 
			res++;
		}
	}
	free_Tree(root);
	cout << res << endl;
	return(0);
}
0