Submission #1403958
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__) void _dbg(string){cout<<endl;} template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);} template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} #define INF 1120000000 using Point = complex<long>; #define X real() #define Y imag() #define LE(n,m) ((n) < (m) + EPS) #define GE(n,m) ((n) + EPS > (m)) #define EQ(n,m) (abs((n)-(m)) < EPS) namespace std { bool operator<(const Point a, const Point b) { return a.X != b.X ? a.X < b.X : a.Y < b.Y; } } // 内積 dot(a,b) = |a||b|cosθ long dot(Point a, Point b){ return a.X*b.X + a.Y*b.Y; } // 外積 cross(a,b) = |a||b|sinθ long cross(Point a, Point b){ return a.X*b.Y - a.Y*b.X; } class AddableConvexHull { public: set<Point> upperHull, lowerHull; AddableConvexHull(){} bool isCovered(set<Point> &hull, Point p){ if(hull.size()==0) return false; if(hull.size()==1){ Point q = *begin(hull); return q.X == p.X && q.Y >= p.Y; } // hull.size() >= 2 auto l = begin(hull); auto r = --end(hull); if(p.X < l->X || p.X > r->X) return false; auto q1 = hull.upper_bound((Point){p.X, INF}); if( q1==end(hull) ){ return (--q1)->Y >= p.Y; } auto q2 = q1--; //dbg(*q1,*q2, q2==end(hull)); // q1.x <= p.x < q2.x return cross(p - *q1, *q2 - *q1) >= 0; } bool inPolygon(Point p){ bool bu = isCovered(upperHull, p); bool bl = isCovered(lowerHull, (Point){p.X, -p.Y}); return bu==true && bl==true; } // only for upper hull void add(set<Point> &hull, Point p){ if(hull.size()==0){ hull.insert(p); return; } if(hull.size()==1){ if(begin(hull)->X == p.X){ Point q = *begin(hull); hull.clear(); hull.insert(max(p,q)); } else { hull.insert(p); } return; } // hull.size() >= 2 if(isCovered(hull, p)) return; // left auto q1 = hull.upper_bound((Point){p.X, INF}); if(q1 != begin(hull)){ q1--; while(hull.size()>1 && q1!=begin(hull)){ auto q2 = q1--; //dbg(*q1,*q2,cross(*q2 - p, *q1 - p)); if( cross(*q2 - p, *q1 - p) > 0 ) break; hull.erase(q2); } } // right q1 = hull.lower_bound((Point){p.X, -INF}); if(q1 != end(hull)){ while(hull.size()>1 && q1 != --end(hull)){ auto q2 = q1++; //dbg(*q1,*q2,cross(*q2 - p, *q1 - p)); if( cross(*q1 - p, *q2 - p) > 0 ) break; hull.erase(q2); } } hull.insert(p); } void add(Point p){ add(upperHull, p); add(lowerHull, (Point){p.X, -p.Y}); // dbg(vector<Point>(all(upperHull))); // dbg(vector<Point>(all(lowerHull))); } }; int main(){ int n; cin>>n; AddableConvexHull hull; rep(i,n){ string s; long x,y; cin>>s>>x>>y; if(s[0]=='M') { hull.add(Point{x,y}); } else { if( hull.inPolygon(Point{x,y}) ) cout << "DANGER" << endl; else cout << "SAFE" << endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 泥棒 |
User | tossy |
Language | C++14 (GCC 5.4.1) |
Score | 300 |
Code Size | 3735 Byte |
Status | AC |
Exec Time | 586 ms |
Memory | 7040 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 | 1 ms | 256 KB |
11_rand01.txt | AC | 1 ms | 256 KB |
11_rand02.txt | AC | 1 ms | 256 KB |
11_rand03.txt | AC | 1 ms | 256 KB |
11_rand04.txt | AC | 1 ms | 256 KB |
11_rand05.txt | AC | 1 ms | 256 KB |
11_rand06.txt | AC | 1 ms | 256 KB |
11_rand07.txt | AC | 1 ms | 256 KB |
11_rand08.txt | AC | 1 ms | 256 KB |
11_rand09.txt | AC | 1 ms | 256 KB |
11_rand10.txt | AC | 1 ms | 256 KB |
11_rand11.txt | AC | 1 ms | 256 KB |
11_rand12.txt | AC | 1 ms | 256 KB |
11_rand13.txt | AC | 1 ms | 256 KB |
11_rand14.txt | AC | 1 ms | 256 KB |
11_rand15.txt | AC | 1 ms | 256 KB |
11_rand16.txt | AC | 1 ms | 256 KB |
11_rand17.txt | AC | 1 ms | 256 KB |
11_rand18.txt | AC | 1 ms | 256 KB |
11_rand19.txt | AC | 1 ms | 256 KB |
11_rand20.txt | AC | 1 ms | 256 KB |
11_rand21.txt | AC | 1 ms | 256 KB |
11_rand22.txt | AC | 1 ms | 256 KB |
11_rand23.txt | AC | 1 ms | 256 KB |
11_rand24.txt | AC | 1 ms | 256 KB |
21_rand00.txt | AC | 2 ms | 256 KB |
21_rand01.txt | AC | 1 ms | 256 KB |
21_rand02.txt | AC | 2 ms | 256 KB |
21_rand03.txt | AC | 2 ms | 256 KB |
21_rand04.txt | AC | 1 ms | 256 KB |
21_rand05.txt | AC | 1 ms | 256 KB |
21_rand06.txt | AC | 2 ms | 256 KB |
21_rand07.txt | AC | 2 ms | 256 KB |
21_rand08.txt | AC | 2 ms | 256 KB |
21_rand09.txt | AC | 1 ms | 256 KB |
21_rand10.txt | AC | 1 ms | 256 KB |
21_rand11.txt | AC | 1 ms | 256 KB |
21_rand12.txt | AC | 1 ms | 256 KB |
21_rand13.txt | AC | 1 ms | 256 KB |
21_rand14.txt | AC | 2 ms | 256 KB |
21_rand15.txt | AC | 2 ms | 256 KB |
21_rand16.txt | AC | 1 ms | 256 KB |
21_rand17.txt | AC | 2 ms | 256 KB |
21_rand18.txt | AC | 1 ms | 256 KB |
21_rand19.txt | AC | 1 ms | 256 KB |
21_rand20.txt | AC | 2 ms | 256 KB |
21_rand21.txt | AC | 1 ms | 256 KB |
21_rand22.txt | AC | 1 ms | 256 KB |
21_rand23.txt | AC | 1 ms | 256 KB |
21_rand24.txt | AC | 1 ms | 256 KB |
31_rand00.txt | AC | 2 ms | 256 KB |
31_rand01.txt | AC | 4 ms | 256 KB |
31_rand02.txt | AC | 4 ms | 256 KB |
31_rand03.txt | AC | 4 ms | 256 KB |
31_rand04.txt | AC | 3 ms | 256 KB |
31_rand05.txt | AC | 5 ms | 256 KB |
31_rand06.txt | AC | 4 ms | 256 KB |
31_rand07.txt | AC | 3 ms | 256 KB |
31_rand08.txt | AC | 5 ms | 256 KB |
31_rand09.txt | AC | 5 ms | 256 KB |
31_rand10.txt | AC | 2 ms | 256 KB |
31_rand11.txt | AC | 4 ms | 256 KB |
31_rand12.txt | AC | 4 ms | 256 KB |
31_rand13.txt | AC | 5 ms | 256 KB |
31_rand14.txt | AC | 2 ms | 256 KB |
31_rand15.txt | AC | 5 ms | 256 KB |
31_rand16.txt | AC | 4 ms | 256 KB |
31_rand17.txt | AC | 2 ms | 256 KB |
31_rand18.txt | AC | 4 ms | 256 KB |
31_rand19.txt | AC | 3 ms | 256 KB |
31_rand20.txt | AC | 2 ms | 256 KB |
31_rand21.txt | AC | 2 ms | 256 KB |
31_rand22.txt | AC | 4 ms | 256 KB |
31_rand23.txt | AC | 4 ms | 256 KB |
31_rand24.txt | AC | 3 ms | 256 KB |
41_rand00.txt | AC | 341 ms | 640 KB |
41_rand01.txt | AC | 191 ms | 512 KB |
41_rand02.txt | AC | 368 ms | 768 KB |
41_rand03.txt | AC | 207 ms | 512 KB |
41_rand04.txt | AC | 243 ms | 512 KB |
41_rand05.txt | AC | 109 ms | 256 KB |
41_rand06.txt | AC | 9 ms | 256 KB |
41_rand07.txt | AC | 298 ms | 768 KB |
41_rand08.txt | AC | 154 ms | 384 KB |
41_rand09.txt | AC | 291 ms | 768 KB |
41_rand10.txt | AC | 399 ms | 768 KB |
41_rand11.txt | AC | 360 ms | 768 KB |
41_rand12.txt | AC | 294 ms | 768 KB |
41_rand13.txt | AC | 322 ms | 768 KB |
41_rand14.txt | AC | 239 ms | 768 KB |
41_rand15.txt | AC | 145 ms | 512 KB |
41_rand16.txt | AC | 327 ms | 640 KB |
41_rand17.txt | AC | 199 ms | 512 KB |
41_rand18.txt | AC | 2 ms | 256 KB |
41_rand19.txt | AC | 3 ms | 256 KB |
41_rand20.txt | AC | 2 ms | 256 KB |
41_rand21.txt | AC | 2 ms | 256 KB |
41_rand22.txt | AC | 2 ms | 256 KB |
41_rand23.txt | AC | 561 ms | 7040 KB |
41_rand24.txt | AC | 586 ms | 7040 KB |