#29281 (C++11) No.202 1円玉投げ

提出ソース

結果

問題	No.202 1円玉投げ
ユーザー	btk
提出日時	2015-05-27 23:00:53
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	202 ms / 5,000 ms
コード長	4,217 bytes
コンパイル時間	1,202 ms
コンパイル使用メモリ	102,508 KB
実行使用メモリ	19,988 KB
最終ジャッジ日時	2024-06-01 20:23:27
合計ジャッジ時間	5,235 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	185 ms 19,856 KB
testcase_01	AC	173 ms 19,876 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	10 ms 6,940 KB
testcase_06	AC	159 ms 16,960 KB
testcase_07	AC	174 ms 18,724 KB
testcase_08	AC	170 ms 18,968 KB
testcase_09	AC	89 ms 11,924 KB
testcase_10	AC	33 ms 6,944 KB
testcase_11	AC	72 ms 10,240 KB
testcase_12	AC	73 ms 10,676 KB
testcase_13	AC	37 ms 7,296 KB
testcase_14	AC	11 ms 6,940 KB
testcase_15	AC	87 ms 11,552 KB
testcase_16	AC	166 ms 19,856 KB
testcase_17	AC	157 ms 19,984 KB
testcase_18	AC	160 ms 19,984 KB
testcase_19	AC	80 ms 10,992 KB
testcase_20	AC	135 ms 15,568 KB
testcase_21	AC	78 ms 10,924 KB
testcase_22	AC	3 ms 6,944 KB
testcase_23	AC	3 ms 6,944 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	3 ms 6,940 KB
testcase_26	AC	3 ms 6,944 KB
testcase_27	AC	4 ms 6,940 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	3 ms 6,940 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	3 ms 6,940 KB
testcase_33	AC	3 ms 6,940 KB
testcase_34	AC	3 ms 6,940 KB
testcase_35	AC	185 ms 19,980 KB
testcase_36	AC	164 ms 19,856 KB
testcase_37	AC	202 ms 19,980 KB
testcase_38	AC	186 ms 19,988 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
}

yukicoder

結果

テストケース

ソースコード