Submission #83823
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <algorithm> // require sort next_permutation count __gcd reverse etc. #include <cstdlib> // require abs exit atof atoi #include <cstdio> // require scanf printf #include <functional> #include <numeric> // require accumulate #include <cmath> // require fabs #include <climits> #include <limits> #include <cfloat> #include <iomanip> // require setw #include <sstream> // require stringstream #include <cstring> // require memset #include <cctype> // require tolower, toupper #include <fstream> // require freopen #include <ctime> // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() using namespace std; #define EPS (1e-10) #define PI (3.141592653589793238462643383279) template<class T> struct point{ T x, y; point &operator+=(const point &a ){ x += a.x; y += a.y; } point &operator-=(const point &a ){ x -= a.x; y -= a.y; } point operator+(const point &a )const{ return (point){x+a.x, y+a.y }; } point operator-(const point &a )const{ return (point){x-a.x, y-a.y }; } operator point<double>()const{ return (point<double>){x, y }; } }; template<class T> point<T> operator*(T c, const point<T> &a ){ return (point<T>){c*a.x, c*a.y }; } point<double> &operator/=(point<double> &a, double c ){ a.x /= c; a.y /= c; return a; } template<class T> point<double> operator/(const point<T> &a, double c ){ return (point<double>){ a.x/c, a.y/c }; } // for integar number template<class T> bool operator<(const point<T> &a, const point<T> &b ){ return (a.x < b.x || ((a.x == b.x ) && (a.y < b.y ) ) ); } template<class T> bool operator==(const point<T> &a, const point<T> &b ){ return a.x == b.x && a.y == b.y; } template<class T> bool operator!=(const point<T> &a, const point<T> &b ){ return a.x != b.x || a.y != b.y; } // for real number bool operator<(const point<double> &a, const point<double> &b ){ return (a.x + EPS < b.x || (abs (a.x - b.x ) < EPS && (a.y + EPS < b.y ) ) ); } bool operator==(const point<double> &a, const point<double> &b ){ return abs (a.x - b.x) < EPS && abs (a.y - b.y ) < EPS; } bool operator!=(const point<double> &a, const point<double> &b ){ return abs (a.x - b.x ) > EPS || abs (a.y - b.y ) > EPS; } // inner product template<class T> T dot(const point<T> &a, const point<T> &b ){ return a.x*b.x + a.y*b.y; } // outer product template<class T> T cross(const point<T> &a, const point<T> &b ){ return a.x*b.y - a.y*b.x; } // distance between origin(0,0) to point a template<class T> double abs(const point<T> &a ){ return sqrt (a.x*a.x + a.y*a.y ); } template<class T> T abs2(const point<T> &a ){ return a.x*a.x + a.y*a.y; } point<double> rot(const point<double> &a, double theta ){ return (point<double>){a.x*cos(theta) - a.y*sin(theta), a.x*sin(theta) + a.y*cos(theta ) }; } // x 軸の正方向を基準とした場合のベクトル a の角度を [0, 2*PI) の範囲で求める template<class T> double arg(const point<T> &a ){ double t = atan2(a.y, a.x ); return t<0.? t+2.*PI : t; } template<class T> struct line{ point<T> a, b; operator line<double>()const{ return (line<double>){a, b}; } }; template<class T> struct segment{ point<T> a, b; operator line<T>()const { return (line<T>){a,b}; } }; template<class T> struct polygon:vector< point<T> >{ polygon(){} polygon(int n ):vector< point<T> >(n){} }; template<class T> struct circle{ point<T> c; T r; }; /* 回転方向 説明 3点の位置関係を求める (A) 座標値が整数 (B) 座標値が実数 引数 a : 点 b : 点 c : 点 戻り値 a-b-c の順に反時計回りに回転しているとき CCW a-b-c の順に時計回りに回転しているとき CW a-b-c が同一直線上にあるとき ON 制約 なし 計算量 O(1) 備考 2 点以上が同一の点であれば常に ON を返すことに注意 */ // (A) enum{CCW = 1, CW = -1, ON = 0 }; template<class T> int ccw(const point<T> &a, const point<T> &b, const point<T> &c ){ T rdir = cross (b-a, c-a ); if (rdir > 0 ) return CCW; if (rdir < 0 ) return CW; return ON; } // (B) //enum{CCW = 1, CW = -1, ON = 0 }; int ccw (const point<double> &a, const point<double> &b, const point<double> &c ){ double rdir = cross (b-a, c-a ); if (rdir > 0 ) return CCW; if (rdir < 0 ) return CW; return ON; } /* 三角形と点の包含判定 説明 三角形 abc が点 p を含むかどうかを判定する 引数 a : 頂点 b : 頂点 c : 頂点 戻り値 含むなら true, 含まないなら false 制約 三角形は縮退していないこと すなわち、三点が同一直線上にないこと、(特に、どの二点も等しくないこと 計算量 O(1) 備考 三角形は CCW でも CW でもよい 点が三角形の境界になるときは含むと判定する Verified: AOJ 0012 A Point in a Triangle AOJ 0143 Altair and Vega */ template<class T> bool cover(const point<T> &a, const point<T> &b, const point<T> &c, const point<T> &p ){ int d1 = ccw (p, a, b ); int d2 = ccw (p, b, c ); int d3 = ccw (p, c, a ); return !((d1 == CCW && d2 == CW ) || (d1 == CCW && d3 == CW ) || (d2 == CCW && d3 == CW ) || (d1 == CW && d2 == CCW ) || (d1 == CW && d3 == CCW ) || (d2 == CW && d3 == CCW ) ); } int main() { // cut here before submit // freopen ("testcase.C1-1", "r", stdin ); int n; cin >> n; polygon<int> M; M.clear(); polygon<int> T; T.clear(); rep (i, n ){ string str; int x, y; cin >> str >> x >> y; if (str == "MONITOR" ){ M.push_back ((point<int>){x,y}); }else{ // if (str == "TARGET" ) T.push_back ((point<int>){x,y}); T.erase (unique (ALL (T ) ), T.end() ); if (M.size() < 3 ){ cout << "SAFE" << endl; }else{ if (cover (M[0], M[1], M[2], T[0] ) || cover (M[0], M[1], M[2], (point<int>){0,0} ) ){ cout << "DANGER" << endl; }else{ cout << "SAFE" << endl; } // end if } // end if } // end if } // end rep return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 泥棒 |
User | ty70 |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 6295 Byte |
Status | WA |
Exec Time | 5031 ms |
Memory | 2988 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 50 | 0 / 50 | 0 / 50 | 0 / 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 | 23 ms | 784 KB |
11_rand01.txt | AC | 20 ms | 780 KB |
11_rand02.txt | WA | 19 ms | 776 KB |
11_rand03.txt | AC | 20 ms | 784 KB |
11_rand04.txt | AC | 21 ms | 780 KB |
11_rand05.txt | AC | 20 ms | 804 KB |
11_rand06.txt | AC | 20 ms | 732 KB |
11_rand07.txt | AC | 20 ms | 784 KB |
11_rand08.txt | WA | 20 ms | 780 KB |
11_rand09.txt | WA | 19 ms | 784 KB |
11_rand10.txt | AC | 20 ms | 788 KB |
11_rand11.txt | WA | 19 ms | 780 KB |
11_rand12.txt | WA | 21 ms | 784 KB |
11_rand13.txt | WA | 20 ms | 784 KB |
11_rand14.txt | AC | 21 ms | 780 KB |
11_rand15.txt | WA | 20 ms | 780 KB |
11_rand16.txt | WA | 20 ms | 784 KB |
11_rand17.txt | AC | 20 ms | 780 KB |
11_rand18.txt | AC | 20 ms | 776 KB |
11_rand19.txt | AC | 21 ms | 776 KB |
11_rand20.txt | AC | 21 ms | 788 KB |
11_rand21.txt | AC | 20 ms | 784 KB |
11_rand22.txt | WA | 19 ms | 780 KB |
11_rand23.txt | AC | 19 ms | 780 KB |
11_rand24.txt | AC | 19 ms | 776 KB |
21_rand00.txt | WA | 22 ms | 780 KB |
21_rand01.txt | WA | 21 ms | 784 KB |
21_rand02.txt | WA | 21 ms | 732 KB |
21_rand03.txt | WA | 21 ms | 784 KB |
21_rand04.txt | AC | 20 ms | 784 KB |
21_rand05.txt | WA | 21 ms | 780 KB |
21_rand06.txt | WA | 21 ms | 776 KB |
21_rand07.txt | WA | 21 ms | 776 KB |
21_rand08.txt | WA | 20 ms | 780 KB |
21_rand09.txt | WA | 21 ms | 780 KB |
21_rand10.txt | WA | 20 ms | 792 KB |
21_rand11.txt | WA | 22 ms | 776 KB |
21_rand12.txt | WA | 18 ms | 780 KB |
21_rand13.txt | WA | 19 ms | 784 KB |
21_rand14.txt | WA | 19 ms | 776 KB |
21_rand15.txt | WA | 19 ms | 776 KB |
21_rand16.txt | WA | 19 ms | 780 KB |
21_rand17.txt | WA | 19 ms | 776 KB |
21_rand18.txt | WA | 19 ms | 784 KB |
21_rand19.txt | WA | 21 ms | 780 KB |
21_rand20.txt | WA | 21 ms | 776 KB |
21_rand21.txt | WA | 21 ms | 788 KB |
21_rand22.txt | WA | 21 ms | 784 KB |
21_rand23.txt | WA | 19 ms | 736 KB |
21_rand24.txt | WA | 18 ms | 784 KB |
31_rand00.txt | WA | 23 ms | 772 KB |
31_rand01.txt | WA | 27 ms | 788 KB |
31_rand02.txt | WA | 26 ms | 776 KB |
31_rand03.txt | WA | 26 ms | 780 KB |
31_rand04.txt | WA | 23 ms | 780 KB |
31_rand05.txt | WA | 29 ms | 784 KB |
31_rand06.txt | WA | 25 ms | 784 KB |
31_rand07.txt | WA | 23 ms | 780 KB |
31_rand08.txt | WA | 28 ms | 784 KB |
31_rand09.txt | WA | 27 ms | 780 KB |
31_rand10.txt | WA | 19 ms | 784 KB |
31_rand11.txt | WA | 28 ms | 776 KB |
31_rand12.txt | WA | 26 ms | 780 KB |
31_rand13.txt | WA | 29 ms | 776 KB |
31_rand14.txt | WA | 21 ms | 776 KB |
31_rand15.txt | WA | 27 ms | 772 KB |
31_rand16.txt | WA | 27 ms | 784 KB |
31_rand17.txt | WA | 22 ms | 784 KB |
31_rand18.txt | WA | 26 ms | 788 KB |
31_rand19.txt | WA | 24 ms | 816 KB |
31_rand20.txt | WA | 22 ms | 780 KB |
31_rand21.txt | WA | 21 ms | 776 KB |
31_rand22.txt | WA | 26 ms | 780 KB |
31_rand23.txt | WA | 25 ms | 776 KB |
31_rand24.txt | WA | 25 ms | 784 KB |
41_rand00.txt | WA | 3608 ms | 2600 KB |
41_rand01.txt | WA | 1406 ms | 1924 KB |
41_rand02.txt | TLE | 5029 ms | 2568 KB |
41_rand03.txt | WA | 1130 ms | 2440 KB |
41_rand04.txt | WA | 2082 ms | 1916 KB |
41_rand05.txt | WA | 200 ms | 1844 KB |
41_rand06.txt | WA | 36 ms | 788 KB |
41_rand07.txt | WA | 4042 ms | 2684 KB |
41_rand08.txt | WA | 775 ms | 1724 KB |
41_rand09.txt | WA | 4372 ms | 2564 KB |
41_rand10.txt | TLE | 5030 ms | 2988 KB |
41_rand11.txt | WA | 4829 ms | 2816 KB |
41_rand12.txt | WA | 4678 ms | 2492 KB |
41_rand13.txt | TLE | 5031 ms | 2476 KB |
41_rand14.txt | WA | 4425 ms | 2088 KB |
41_rand15.txt | WA | 1485 ms | 1584 KB |
41_rand16.txt | WA | 3541 ms | 2492 KB |
41_rand17.txt | WA | 1025 ms | 2356 KB |
41_rand18.txt | WA | 21 ms | 780 KB |
41_rand19.txt | WA | 21 ms | 768 KB |
41_rand20.txt | WA | 22 ms | 716 KB |
41_rand21.txt | WA | 21 ms | 780 KB |
41_rand22.txt | WA | 21 ms | 780 KB |
41_rand23.txt | TLE | 5030 ms | 2696 KB |
41_rand24.txt | TLE | 5030 ms | 2776 KB |