結果
問題 | No.202 1円玉投げ |
ユーザー | btk |
提出日時 | 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 |
ソースコード
#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); }