Submission #363487
Source Code Expand
#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> using namespace std; #define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++) #define rE(i,b) reE(i,0,b) #define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++) #define rT(i,b) reT(i,0,b) #define rep(i,a,b) reE(i,a,b); #define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--) #define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i)) #define rti(i,b) for(auto (i)=(b).rbegin();(i)!=(b).rend();++(i)) #define LL long long #define all(b) (b).begin(),(b).end() #define input_init stringstream ss; string strtoken, token; istringstream is #define input_line getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit) #define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num #define dir(xx,yy,x,y,i) (xx)=(x)+dir[(i)],(yy)=(y)+dir[(i)+1] typedef complex<double> P; typedef vector<P> Poly; const LL INF = 1 << 30; const double eps = 1e-9; const int dir[] = { 0, 1, 0, -1, 0 }; inline double dot(const P a, const P b){//A dot B return a.real()*b.real() + a.imag()*b.imag(); } inline double cross(const P a, const P b){//A cross B return a.real()*b.imag() - a.imag()*b.real(); } struct dynamic_convex{ double priority; P xy; dynamic_convex(double p, P _xy){ priority = p; xy = _xy; } bool operator>( const dynamic_convex &another)const{ return(priority > another.priority); } bool operator>=(const dynamic_convex &another)const{ return(priority >= another.priority); } bool operator<(const dynamic_convex &another)const{ return(priority < another.priority); } bool operator<=(const dynamic_convex &another)const{ return(priority <= another.priority); } bool operator==(const dynamic_convex &another)const{ return(priority == another.priority); } bool operator!=(const dynamic_convex &another)const{ return(priority != another.priority); } }; template <class T> struct avl_tree { struct node { T key; int size, height; node *child[2]; node(const T &key) : key(key), size(1), height(1) { child[0] = child[1] = 0; } } *root; typedef node *pointer; avl_tree() { root = NULL; } pointer find(const T &key) { return find(root, key); } node *find(node *t, const T &key) { if (t == NULL) return NULL; if (key == t->key) return t; else if (key < t->key) return find(t->child[0], key); else return find(t->child[1], key); } void insert(const T &key) { root = insert(root, new node(key)); } node *insert(node *t, node *x) { if (t == NULL) return x; if (x->key <= t->key) t->child[0] = insert(t->child[0], x); else t->child[1] = insert(t->child[1], x); t->size += 1; return balance(t); } void erase(const T &key) { root = erase(root, key); } node *erase(node *t,const T &x) { if (t == NULL) return NULL; if (t->key==x) { return move_down(t->child[0], t->child[1]); } else { if (x < t->key) t->child[0] = erase(t->child[0], x); else t->child[1] = erase(t->child[1], x); t->size -= 1; return balance(t); } } node *move_down(node *t, node *rhs) { if (t == NULL) return rhs; t->child[1] = move_down(t->child[1], rhs); return balance(t); } #define sz(t) (t ? t->size : 0) #define ht(t) (t ? t->height : 0) node *rotate(node *t, int l, int r) { node *s = t->child[r]; t->child[r] = s->child[l]; s->child[l] = balance(t); if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; if (s) s->size = sz(s->child[0]) + sz(s->child[1]) + 1; return balance(s); } node *balance(node *t) { for (int i = 0; i < 2; ++i) { if (ht(t->child[!i]) - ht(t->child[i]) < -1) { if (ht(t->child[i]->child[!i]) - ht(t->child[i]->child[i]) > 0) t->child[i] = rotate(t->child[i], i, !i); return rotate(t, !i, i); } } if (t) t->height = max(ht(t->child[0]), ht(t->child[1])) + 1; if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; return t; } pointer rank(int k) const { return rank(root, k); } pointer rank(node *t, int k) const { if (!t) return NULL; int m = sz(t->child[0]); if (k < m) return rank(t->child[0], k); if (k == m) return t; return rank(t->child[1], k - m - 1); } T &operator[](int index){ return rank(index)->key; } }; typedef avl_tree<dynamic_convex> DC; const double divi = 1 << 15; #define rs(x) (x).root->size bool dc_in(DC& t,P &p){ if (t.root == NULL)return false; if (rs(t) == 1)return (t[0].xy == p); if (rs(t) == 2)return(abs(t[0].xy - p) + abs(t[1].xy - p) - abs(t[0].xy - t[1].xy) < eps); int a = 0, b = rs(t), c; double A, C; const P g = (t[a].xy + t[b - 1].xy + t[b / 2].xy) / 3.0; while (b - a > 1){ c = (a + b) / 2; A = cross(t[a].xy - g, p - t[a].xy); C = cross(t[c].xy - g, p - t[c].xy); if (cross(t[a].xy - g, t[c].xy - g) > -eps){ if (A>-eps&&C < -eps)b = c; else a = c; } else { if (C < -eps || A > -eps)b = c; else a = c; } } return(cross(t[b%rs(t)].xy - t[a].xy, p - t[b%rs(t)].xy) > -eps); } #define ix(i) (rs(t)+(i))%rs(t) void dc_hull(DC &t, P &p){ if (t.root == NULL){ t.insert(dynamic_convex(0, p)); return; } if (rs(t) == 1){ if (t.root->key.xy != p)t.insert(dynamic_convex(1, p)); return; } if (rs(t) == 2){ double j = cross(t[1].xy - t[0].xy, p - t[1].xy); if (j > eps)t.insert(dynamic_convex(2, p)); else if (j < -eps)t.insert(dynamic_convex(0.5, p)); else{ j = abs(t[0].xy - t[1].xy); double f = abs(t[0].xy - p), k = abs(p - t[1].xy); if (f - k > eps&&f - j > eps)t[1].xy = p; else if (f + k - j > eps)t[0].xy = p; } return; } int a = 0, b = rs(t), c; double A, C; const P g = (t[a].xy + t[b - 1].xy + t[b / 2].xy) / 3.0; while (b - a > 1){ c = (a + b) / 2; A = cross(t[a].xy - g, p - t[a].xy); C = cross(t[c].xy - g, p - t[c].xy); if (cross(t[a].xy - g, t[c].xy - g) > -eps){ if (A > -eps&&C < -eps)b = c; else a = c; } else { if (C < -eps || A > -eps)b = c; else a = c; } } if (cross(t[b%rs(t)].xy - t[a].xy, p - t[b%rs(t)].xy) > -eps)return; while (cross(t[ix(a)].xy - t[ix(a - 1)].xy, p - t[ix(a)].xy)<-eps){ t.erase(t[ix(a)]); a=ix(a-1); b=a+1; } while (cross(t[ix(b)].xy - p, t[ix(b + 1)].xy - t[ix(b)].xy)<-eps) if (b == rs(t)){t.erase(t[ix(b)]); a=ix(a-1); b=a+1; } else t.erase(t[ix(b)]); double tmp; if (ix(b) == 0)tmp = t[ix(a)].priority + 1.0; else tmp = (t[ix(a)].priority + t[ix(b)].priority) / 2.0; t.insert(dynamic_convex(tmp, p)); } DC dc; //ofstream fout("output.txt"); int main(){ int N; string s; double x, y; cin >> N; rT(i,N){ cin >> s >> x >> y; //x /= divi; //y /= divi; P p(x, y); if (s == "MONITOR"){ dc_hull(dc, p); } else{ // cout << p << endl; if (dc_in(dc, p))cout << "DANGER" << endl; else cout << "SAFE" << endl; } // if (dc.root != NULL){ rT(i, rs(dc))cout << dc[i].xy; cout << endl; } } return(0); } /* 5 MONITOR 0 0 MONITOR 2 2 MONITOR 0 2 MONITOR 2 0 TARGET 2 2 */
Submission Info
Submission Time | |
---|---|
Task | C - 泥棒 |
User | btk15049 |
Language | C++11 (GCC 4.8.1) |
Score | 300 |
Code Size | 7395 Byte |
Status | AC |
Exec Time | 4245 ms |
Memory | 7000 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | 50 / 50 | 150 / 150 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt |
Subtask2 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt |
Subtask3 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt |
Subtask4 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt, 41_rand00.txt, 41_rand01.txt, 41_rand02.txt, 41_rand03.txt, 41_rand04.txt, 41_rand05.txt, 41_rand06.txt, 41_rand07.txt, 41_rand08.txt, 41_rand09.txt, 41_rand10.txt, 41_rand11.txt, 41_rand12.txt, 41_rand13.txt, 41_rand14.txt, 41_rand15.txt, 41_rand16.txt, 41_rand17.txt, 41_rand18.txt, 41_rand19.txt, 41_rand20.txt, 41_rand21.txt, 41_rand22.txt, 41_rand23.txt, 41_rand24.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
11_rand00.txt | AC | 25 ms | 804 KB |
11_rand01.txt | AC | 31 ms | 672 KB |
11_rand02.txt | AC | 25 ms | 676 KB |
11_rand03.txt | AC | 24 ms | 676 KB |
11_rand04.txt | AC | 24 ms | 676 KB |
11_rand05.txt | AC | 26 ms | 800 KB |
11_rand06.txt | AC | 24 ms | 928 KB |
11_rand07.txt | AC | 26 ms | 800 KB |
11_rand08.txt | AC | 24 ms | 800 KB |
11_rand09.txt | AC | 25 ms | 740 KB |
11_rand10.txt | AC | 25 ms | 804 KB |
11_rand11.txt | AC | 23 ms | 804 KB |
11_rand12.txt | AC | 25 ms | 796 KB |
11_rand13.txt | AC | 26 ms | 804 KB |
11_rand14.txt | AC | 24 ms | 676 KB |
11_rand15.txt | AC | 25 ms | 804 KB |
11_rand16.txt | AC | 25 ms | 676 KB |
11_rand17.txt | AC | 25 ms | 804 KB |
11_rand18.txt | AC | 24 ms | 800 KB |
11_rand19.txt | AC | 24 ms | 800 KB |
11_rand20.txt | AC | 26 ms | 680 KB |
11_rand21.txt | AC | 25 ms | 676 KB |
11_rand22.txt | AC | 26 ms | 800 KB |
11_rand23.txt | AC | 26 ms | 804 KB |
11_rand24.txt | AC | 26 ms | 740 KB |
21_rand00.txt | AC | 25 ms | 676 KB |
21_rand01.txt | AC | 24 ms | 676 KB |
21_rand02.txt | AC | 25 ms | 928 KB |
21_rand03.txt | AC | 27 ms | 804 KB |
21_rand04.txt | AC | 25 ms | 928 KB |
21_rand05.txt | AC | 26 ms | 720 KB |
21_rand06.txt | AC | 26 ms | 676 KB |
21_rand07.txt | AC | 26 ms | 796 KB |
21_rand08.txt | AC | 26 ms | 800 KB |
21_rand09.txt | AC | 23 ms | 800 KB |
21_rand10.txt | AC | 26 ms | 804 KB |
21_rand11.txt | AC | 27 ms | 804 KB |
21_rand12.txt | AC | 25 ms | 928 KB |
21_rand13.txt | AC | 26 ms | 676 KB |
21_rand14.txt | AC | 28 ms | 932 KB |
21_rand15.txt | AC | 26 ms | 928 KB |
21_rand16.txt | AC | 24 ms | 804 KB |
21_rand17.txt | AC | 25 ms | 924 KB |
21_rand18.txt | AC | 26 ms | 740 KB |
21_rand19.txt | AC | 25 ms | 800 KB |
21_rand20.txt | AC | 27 ms | 796 KB |
21_rand21.txt | AC | 27 ms | 804 KB |
21_rand22.txt | AC | 27 ms | 752 KB |
21_rand23.txt | AC | 24 ms | 928 KB |
21_rand24.txt | AC | 23 ms | 800 KB |
31_rand00.txt | AC | 30 ms | 804 KB |
31_rand01.txt | AC | 33 ms | 800 KB |
31_rand02.txt | AC | 32 ms | 800 KB |
31_rand03.txt | AC | 36 ms | 808 KB |
31_rand04.txt | AC | 30 ms | 676 KB |
31_rand05.txt | AC | 32 ms | 792 KB |
31_rand06.txt | AC | 32 ms | 808 KB |
31_rand07.txt | AC | 29 ms | 800 KB |
31_rand08.txt | AC | 37 ms | 804 KB |
31_rand09.txt | AC | 32 ms | 676 KB |
31_rand10.txt | AC | 28 ms | 676 KB |
31_rand11.txt | AC | 34 ms | 800 KB |
31_rand12.txt | AC | 31 ms | 800 KB |
31_rand13.txt | AC | 36 ms | 928 KB |
31_rand14.txt | AC | 26 ms | 804 KB |
31_rand15.txt | AC | 34 ms | 800 KB |
31_rand16.txt | AC | 34 ms | 808 KB |
31_rand17.txt | AC | 27 ms | 804 KB |
31_rand18.txt | AC | 32 ms | 676 KB |
31_rand19.txt | AC | 29 ms | 800 KB |
31_rand20.txt | AC | 25 ms | 680 KB |
31_rand21.txt | AC | 26 ms | 676 KB |
31_rand22.txt | AC | 33 ms | 808 KB |
31_rand23.txt | AC | 32 ms | 676 KB |
31_rand24.txt | AC | 32 ms | 924 KB |
41_rand00.txt | AC | 826 ms | 928 KB |
41_rand01.txt | AC | 471 ms | 800 KB |
41_rand02.txt | AC | 875 ms | 796 KB |
41_rand03.txt | AC | 511 ms | 808 KB |
41_rand04.txt | AC | 603 ms | 808 KB |
41_rand05.txt | AC | 269 ms | 928 KB |
41_rand06.txt | AC | 45 ms | 928 KB |
41_rand07.txt | AC | 716 ms | 804 KB |
41_rand08.txt | AC | 388 ms | 808 KB |
41_rand09.txt | AC | 697 ms | 800 KB |
41_rand10.txt | AC | 968 ms | 800 KB |
41_rand11.txt | AC | 868 ms | 808 KB |
41_rand12.txt | AC | 728 ms | 804 KB |
41_rand13.txt | AC | 753 ms | 804 KB |
41_rand14.txt | AC | 572 ms | 928 KB |
41_rand15.txt | AC | 356 ms | 808 KB |
41_rand16.txt | AC | 824 ms | 800 KB |
41_rand17.txt | AC | 489 ms | 804 KB |
41_rand18.txt | AC | 29 ms | 796 KB |
41_rand19.txt | AC | 27 ms | 800 KB |
41_rand20.txt | AC | 27 ms | 804 KB |
41_rand21.txt | AC | 28 ms | 804 KB |
41_rand22.txt | AC | 28 ms | 676 KB |
41_rand23.txt | AC | 3715 ms | 7000 KB |
41_rand24.txt | AC | 4245 ms | 6940 KB |