Submission #84648


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-6)
#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();
	polygon<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.clear();
			T.push_back ((point<double>){0,0});
			T.push_back ((point<double>){x,y});
			if (M.size() == 1 ){
				rep (i, T.size() ){
					if (abs(M[0] - T[i] ) < EPS ){
						ok = false;
						break;
					} // end if
				} // end rep					
			}else
			if (M.size() == 2 ){
				rep (i, T.size() ){
					rep (j, M.size() ){
						if (abs(M[j] - T[i] ) < EPS ){
							ok = false;
							break;
						} // end if
					} // end rep
				} // end rep					

				rep (i, T.size() ){
					if (cover ((segment<double>){M[0],M[1]},T[i]) ){
						ok = false;
						break;
					} // end if
				} // end rep					
			}else
			if (M.size() == 3 ){
				rep (i, T.size() ){
					rep (j, M.size() ){
						if (abs(M[j] - T[i] ) < EPS ){
							ok = false;
							break;
						} // end if
					} // end rep
				} // end rep
				rep (i, T.size() ){
					rep (j, M.size() ){
						if (cover ((segment<double>){M[j], M[(j+1)%M.size()]},T[i] ) ){
							ok = false;
							break;
						} // end if
					} // end rep
				} // end rep
				rep (i, T.size() ){
					if (cover (M[0], M[1], M[2], T[i] ) ){
						ok = false;
						break;
					} // end if
				} // 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 9160 Byte
Status WA
Exec Time 1075 ms
Memory 3244 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 50 0 / 50 0 / 50 0 / 150
Status
AC × 24
WA × 1
AC × 26
WA × 24
AC × 26
WA × 49
AC × 26
WA × 74
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 22 ms 824 KB
11_rand01.txt AC 22 ms 668 KB
11_rand02.txt AC 21 ms 792 KB
11_rand03.txt AC 20 ms 696 KB
11_rand04.txt AC 20 ms 668 KB
11_rand05.txt AC 20 ms 704 KB
11_rand06.txt AC 20 ms 796 KB
11_rand07.txt AC 20 ms 788 KB
11_rand08.txt AC 19 ms 784 KB
11_rand09.txt AC 20 ms 784 KB
11_rand10.txt AC 19 ms 788 KB
11_rand11.txt AC 21 ms 788 KB
11_rand12.txt AC 18 ms 788 KB
11_rand13.txt AC 20 ms 816 KB
11_rand14.txt AC 19 ms 788 KB
11_rand15.txt AC 21 ms 784 KB
11_rand16.txt AC 20 ms 788 KB
11_rand17.txt AC 21 ms 792 KB
11_rand18.txt AC 20 ms 788 KB
11_rand19.txt AC 20 ms 692 KB
11_rand20.txt AC 20 ms 668 KB
11_rand21.txt AC 19 ms 740 KB
11_rand22.txt WA 20 ms 788 KB
11_rand23.txt AC 18 ms 792 KB
11_rand24.txt AC 18 ms 792 KB
21_rand00.txt WA 23 ms 672 KB
21_rand01.txt WA 20 ms 660 KB
21_rand02.txt WA 21 ms 696 KB
21_rand03.txt WA 19 ms 784 KB
21_rand04.txt AC 20 ms 792 KB
21_rand05.txt WA 20 ms 788 KB
21_rand06.txt WA 21 ms 796 KB
21_rand07.txt WA 20 ms 660 KB
21_rand08.txt WA 20 ms 792 KB
21_rand09.txt WA 20 ms 788 KB
21_rand10.txt WA 19 ms 784 KB
21_rand11.txt WA 20 ms 792 KB
21_rand12.txt AC 21 ms 636 KB
21_rand13.txt WA 22 ms 812 KB
21_rand14.txt WA 20 ms 784 KB
21_rand15.txt WA 22 ms 788 KB
21_rand16.txt WA 20 ms 784 KB
21_rand17.txt WA 21 ms 820 KB
21_rand18.txt WA 19 ms 784 KB
21_rand19.txt WA 20 ms 784 KB
21_rand20.txt WA 20 ms 788 KB
21_rand21.txt WA 22 ms 796 KB
21_rand22.txt WA 19 ms 792 KB
21_rand23.txt WA 19 ms 784 KB
21_rand24.txt WA 20 ms 788 KB
31_rand00.txt WA 22 ms 788 KB
31_rand01.txt WA 27 ms 752 KB
31_rand02.txt WA 27 ms 788 KB
31_rand03.txt WA 27 ms 784 KB
31_rand04.txt WA 26 ms 692 KB
31_rand05.txt WA 30 ms 688 KB
31_rand06.txt WA 26 ms 784 KB
31_rand07.txt WA 28 ms 648 KB
31_rand08.txt WA 28 ms 788 KB
31_rand09.txt WA 27 ms 784 KB
31_rand10.txt WA 20 ms 784 KB
31_rand11.txt WA 27 ms 788 KB
31_rand12.txt WA 29 ms 788 KB
31_rand13.txt WA 29 ms 772 KB
31_rand14.txt WA 19 ms 788 KB
31_rand15.txt WA 26 ms 664 KB
31_rand16.txt WA 29 ms 692 KB
31_rand17.txt WA 22 ms 692 KB
31_rand18.txt WA 26 ms 764 KB
31_rand19.txt WA 25 ms 788 KB
31_rand20.txt WA 23 ms 792 KB
31_rand21.txt WA 21 ms 784 KB
31_rand22.txt WA 26 ms 784 KB
31_rand23.txt WA 28 ms 788 KB
31_rand24.txt WA 25 ms 788 KB
41_rand00.txt WA 770 ms 3112 KB
41_rand01.txt WA 440 ms 1964 KB
41_rand02.txt WA 838 ms 3244 KB
41_rand03.txt WA 455 ms 2988 KB
41_rand04.txt WA 554 ms 2096 KB
41_rand05.txt WA 240 ms 2856 KB
41_rand06.txt WA 38 ms 812 KB
41_rand07.txt WA 718 ms 2096 KB
41_rand08.txt WA 357 ms 1840 KB
41_rand09.txt WA 679 ms 2104 KB
41_rand10.txt WA 904 ms 3112 KB
41_rand11.txt WA 826 ms 3108 KB
41_rand12.txt WA 697 ms 2092 KB
41_rand13.txt WA 758 ms 2088 KB
41_rand14.txt WA 584 ms 1208 KB
41_rand15.txt WA 355 ms 1208 KB
41_rand16.txt WA 747 ms 3112 KB
41_rand17.txt WA 437 ms 2988 KB
41_rand18.txt WA 22 ms 788 KB
41_rand19.txt WA 24 ms 788 KB
41_rand20.txt WA 22 ms 704 KB
41_rand21.txt WA 21 ms 784 KB
41_rand22.txt WA 22 ms 792 KB
41_rand23.txt WA 1050 ms 3108 KB
41_rand24.txt WA 1075 ms 3112 KB