結果

問題 No.202 1円玉投げ
ユーザー btkbtk
提出日時 2015-05-27 23:00:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 235 ms / 5,000 ms
コード長 4,217 bytes
コンパイル時間 894 ms
コンパイル使用メモリ 101,448 KB
実行使用メモリ 20,096 KB
最終ジャッジ日時 2023-08-23 22:57:10
合計ジャッジ時間 6,059 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 200 ms
20,096 KB
testcase_01 AC 196 ms
19,836 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 11 ms
4,416 KB
testcase_06 AC 183 ms
17,168 KB
testcase_07 AC 214 ms
18,680 KB
testcase_08 AC 218 ms
18,936 KB
testcase_09 AC 108 ms
11,732 KB
testcase_10 AC 41 ms
6,688 KB
testcase_11 AC 86 ms
10,188 KB
testcase_12 AC 89 ms
10,468 KB
testcase_13 AC 46 ms
7,092 KB
testcase_14 AC 13 ms
4,456 KB
testcase_15 AC 103 ms
11,544 KB
testcase_16 AC 176 ms
19,948 KB
testcase_17 AC 176 ms
20,092 KB
testcase_18 AC 175 ms
20,040 KB
testcase_19 AC 95 ms
11,048 KB
testcase_20 AC 164 ms
15,640 KB
testcase_21 AC 95 ms
11,108 KB
testcase_22 AC 3 ms
4,380 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 3 ms
4,376 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 4 ms
4,380 KB
testcase_33 AC 3 ms
4,380 KB
testcase_34 AC 3 ms
4,376 KB
testcase_35 AC 190 ms
19,976 KB
testcase_36 AC 182 ms
20,076 KB
testcase_37 AC 235 ms
20,004 KB
testcase_38 AC 195 ms
19,896 KB
testcase_39 AC 2 ms
4,380 KB
testcase_40 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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