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

• 問題: No.202 1円玉投げ
• ユーザー: btk
• 提出日時: 2015-05-27 22:50:59
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 3,960 bytes
• コンパイル時間: 1,028 ms
• コンパイル使用メモリ: 96,744 KB
• 実行使用メモリ: 13,732 KB
• 最終ジャッジ日時: 2024-06-01 20:23:03
• 合計ジャッジ時間: 5,043 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	161 ms; 13,604 KB
testcase_01	AC	143 ms; 13,548 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	9 ms; 5,376 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	30 ms; 5,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	34 ms; 5,760 KB
testcase_14	AC	11 ms; 5,376 KB
testcase_15	AC	74 ms; 8,540 KB
testcase_16	AC	132 ms; 13,732 KB
testcase_17	AC	139 ms; 13,608 KB
testcase_18	AC	140 ms; 13,700 KB
testcase_19	AC	70 ms; 8,048 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	3 ms; 5,376 KB
testcase_23	AC	4 ms; 5,376 KB
testcase_24	AC	3 ms; 5,376 KB
testcase_25	AC	4 ms; 5,376 KB
testcase_26	AC	3 ms; 5,376 KB
testcase_27	AC	4 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	4 ms; 5,376 KB
testcase_30	AC	3 ms; 5,376 KB
testcase_31	RE	-
testcase_32	AC	3 ms; 5,376 KB
testcase_33	WA	-
testcase_34	AC	4 ms; 5,376 KB
testcase_35	AC	164 ms; 13,728 KB
testcase_36	AC	154 ms; 13,728 KB
testcase_37	WA	-
testcase_38	AC	166 ms; 13,608 KB
testcase_39	AC	3 ms; 5,376 KB
testcase_40	AC	2 ms; 5,376 KB

ソースコード

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

#define all(_b) (_b).begin(),(_b).end()
int main(void){
	int n,res=0;
	cin >> n;
	VP input(n);

	for (int i = 0; i < n; i++){
		cin >> input[i].x >> input[i].y;
		input[i].id = i;
	}
	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);
}