Submission #84603
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-9) #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; } /* 点と点の距離 説明 点と点の距離を求める dist : 距離そのもの dist2 : 距離の二乗 引数 a : 点 b : 点 戻り値 点 a と 点 b の距離 制約 なし 計算量 O(1) 備考 */ template<class T> double dist(const point<T> &a, const point<T> &b ){ return sqrt ((a.x - b.x )*(a.x - b.x ) + (a.y - b.y )*(a.y - b.y ) ); } template<class T> T dist2(const point<T> &a, const point<T> &b ){ return (a.x - b.x )*(a.x - b.x ) + (a.y - b.y )*(a.y - b.y ); } /* 線分と点の距離 説明 線分と点の距離を求める dist : 距離そのもの dist2 : 距離の2乗 引数 S : 線分 p : 点 戻り値 線分 S と点 p の距離 計算量 O(1) 備考 dist2 は <= 0 で正しい。(ESP を使わなくてよい. ) */ template<class T> double dist(const segment<T> &S, const point<T> &p ){ if (dot (S.b-S.a, p-S.a ) <= 0 ) return dist (p, S.a ); if (dot (S.a-S.b, p-S.b ) <= 0 ) return dist (p, S.b ); return abs (cross (S.b-S.a, p - S.a ) )/dist (S.a, S.b ); } template<class T> double dist2(const segment<T> &S, const point<T> &p ){ if (dot (S.b-S.a, p-S.a ) <= 0 ) return dist2 (p, S.a ); if (dot (S.a-S.b, p-S.b ) <= 0 ) return dist2 (p, S.b ); return (double)cross (S.b-S.a, p - S.a )*cross (S.b-S.a, p - S.a )/dist (S.a, S.b ); } /* 線分と点の包含判定 説明 線分が点を含むかどうかを判定する (A) 座標値が整数 (B) 座標値が実数 引数 S : 線分 p : 点 戻り値 含むなら true, 含まないなら false 制約 なし 計算量 O(1) 備考 Verified: AOJ 2003 Railroad Conflict */ // (A) // TODO // (B) bool cover(const segment<double> &S, const point<double> &p ){ return dist(S.a,p)+dist(p,S.b)<dist(S.a,S.b)+EPS; } /* 三角形と点の包含判定 説明 三角形 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<double> M; M.clear(); point<double> T; rep (i, n ){ string str; double x, y; cin >> str >> x >> y; if (str == "MONITOR" ){ M.push_back ((point<double>){x,y}); }else{ // if (str == "TARGET" ) bool ok = true; T = ((point<double>){x,y}); if (M.size() == 1 ){ rep (i, 2 ){ if (abs(M[0] - T ) < EPS ){ ok = false; break; } // end if T = (point<double>){0,0}; } // end rep }else if (M.size() == 2 ){ rep (i, 2 ){ if (cover ((segment<double>){M[0],M[1]},T) ){ ok = false; break; } // end if T = (point<double>){0,0}; } // end rep }else if (M.size() == 3 ){ rep (i, 2 ){ if (cover ((segment<double>){M[0],M[1]},T) || cover ((segment<double>){M[1],M[2]},T) || cover ((segment<double>){M[2],M[0]},T) || cover (M[0], M[1], M[2], T ) ){ ok = false; break; } // end if T = (point<double>){0,0}; } // end rep } // end if if (ok ){ cout << "SAFE" << endl; }else{ cout << "DANGER" << endl; } // 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 | 8722 Byte |
Status | WA |
Exec Time | 1066 ms |
Memory | 3236 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 | 20 ms | 792 KB |
11_rand01.txt | AC | 20 ms | 792 KB |
11_rand02.txt | AC | 19 ms | 788 KB |
11_rand03.txt | AC | 21 ms | 820 KB |
11_rand04.txt | AC | 19 ms | 784 KB |
11_rand05.txt | AC | 20 ms | 784 KB |
11_rand06.txt | AC | 21 ms | 788 KB |
11_rand07.txt | AC | 19 ms | 784 KB |
11_rand08.txt | AC | 20 ms | 688 KB |
11_rand09.txt | AC | 21 ms | 788 KB |
11_rand10.txt | AC | 21 ms | 784 KB |
11_rand11.txt | AC | 20 ms | 792 KB |
11_rand12.txt | AC | 22 ms | 780 KB |
11_rand13.txt | AC | 20 ms | 692 KB |
11_rand14.txt | AC | 19 ms | 792 KB |
11_rand15.txt | AC | 22 ms | 784 KB |
11_rand16.txt | WA | 21 ms | 792 KB |
11_rand17.txt | AC | 20 ms | 784 KB |
11_rand18.txt | AC | 21 ms | 816 KB |
11_rand19.txt | AC | 19 ms | 784 KB |
11_rand20.txt | AC | 19 ms | 788 KB |
11_rand21.txt | AC | 19 ms | 780 KB |
11_rand22.txt | WA | 19 ms | 784 KB |
11_rand23.txt | AC | 20 ms | 784 KB |
11_rand24.txt | AC | 20 ms | 788 KB |
21_rand00.txt | WA | 21 ms | 660 KB |
21_rand01.txt | WA | 23 ms | 796 KB |
21_rand02.txt | WA | 20 ms | 788 KB |
21_rand03.txt | WA | 20 ms | 792 KB |
21_rand04.txt | AC | 19 ms | 788 KB |
21_rand05.txt | WA | 21 ms | 812 KB |
21_rand06.txt | WA | 21 ms | 784 KB |
21_rand07.txt | WA | 21 ms | 700 KB |
21_rand08.txt | WA | 21 ms | 796 KB |
21_rand09.txt | WA | 20 ms | 788 KB |
21_rand10.txt | WA | 20 ms | 792 KB |
21_rand11.txt | WA | 19 ms | 792 KB |
21_rand12.txt | AC | 19 ms | 788 KB |
21_rand13.txt | WA | 19 ms | 788 KB |
21_rand14.txt | WA | 21 ms | 812 KB |
21_rand15.txt | WA | 22 ms | 784 KB |
21_rand16.txt | WA | 20 ms | 784 KB |
21_rand17.txt | WA | 23 ms | 696 KB |
21_rand18.txt | WA | 20 ms | 796 KB |
21_rand19.txt | WA | 20 ms | 796 KB |
21_rand20.txt | WA | 21 ms | 788 KB |
21_rand21.txt | WA | 21 ms | 788 KB |
21_rand22.txt | WA | 22 ms | 792 KB |
21_rand23.txt | WA | 20 ms | 792 KB |
21_rand24.txt | WA | 19 ms | 792 KB |
31_rand00.txt | WA | 23 ms | 788 KB |
31_rand01.txt | WA | 27 ms | 696 KB |
31_rand02.txt | WA | 28 ms | 788 KB |
31_rand03.txt | WA | 26 ms | 788 KB |
31_rand04.txt | WA | 22 ms | 792 KB |
31_rand05.txt | WA | 28 ms | 792 KB |
31_rand06.txt | WA | 25 ms | 812 KB |
31_rand07.txt | WA | 25 ms | 788 KB |
31_rand08.txt | WA | 29 ms | 792 KB |
31_rand09.txt | WA | 28 ms | 700 KB |
31_rand10.txt | WA | 23 ms | 744 KB |
31_rand11.txt | WA | 29 ms | 796 KB |
31_rand12.txt | WA | 26 ms | 796 KB |
31_rand13.txt | WA | 28 ms | 788 KB |
31_rand14.txt | WA | 21 ms | 684 KB |
31_rand15.txt | WA | 26 ms | 788 KB |
31_rand16.txt | WA | 28 ms | 788 KB |
31_rand17.txt | WA | 22 ms | 792 KB |
31_rand18.txt | WA | 26 ms | 796 KB |
31_rand19.txt | WA | 24 ms | 784 KB |
31_rand20.txt | WA | 22 ms | 776 KB |
31_rand21.txt | WA | 24 ms | 656 KB |
31_rand22.txt | WA | 26 ms | 788 KB |
31_rand23.txt | WA | 27 ms | 792 KB |
31_rand24.txt | WA | 25 ms | 664 KB |
41_rand00.txt | WA | 784 ms | 3068 KB |
41_rand01.txt | WA | 439 ms | 1888 KB |
41_rand02.txt | WA | 851 ms | 3236 KB |
41_rand03.txt | WA | 456 ms | 2992 KB |
41_rand04.txt | WA | 558 ms | 2088 KB |
41_rand05.txt | WA | 239 ms | 2832 KB |
41_rand06.txt | WA | 36 ms | 792 KB |
41_rand07.txt | WA | 692 ms | 1964 KB |
41_rand08.txt | WA | 360 ms | 1960 KB |
41_rand09.txt | WA | 699 ms | 2096 KB |
41_rand10.txt | WA | 910 ms | 3116 KB |
41_rand11.txt | WA | 839 ms | 3112 KB |
41_rand12.txt | WA | 702 ms | 2216 KB |
41_rand13.txt | WA | 777 ms | 2088 KB |
41_rand14.txt | WA | 597 ms | 1204 KB |
41_rand15.txt | WA | 353 ms | 1212 KB |
41_rand16.txt | WA | 748 ms | 3120 KB |
41_rand17.txt | WA | 434 ms | 2984 KB |
41_rand18.txt | WA | 21 ms | 784 KB |
41_rand19.txt | WA | 22 ms | 784 KB |
41_rand20.txt | WA | 21 ms | 784 KB |
41_rand21.txt | WA | 22 ms | 788 KB |
41_rand22.txt | WA | 22 ms | 772 KB |
41_rand23.txt | WA | 1066 ms | 3108 KB |
41_rand24.txt | WA | 1035 ms | 3116 KB |