Submission #84834


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;
};

// 点 p を直線 L 上に射影した点を求める
// 	Verified: AOJ 0081 A Symmetric Point
template<class T>
point<double> proj(const point<T> &p, const line<T> &L ){
	return L.a + dot (p-L.a, L.b-L.a )/abs2 (L.b - L.a )*(L.b - L.a );
}

/*
	三角形の面積(外積)

	説明
		三頂点で定まる三角形の面積(の2倍)を求める
	引数
		a : 頂点
		b : 頂点
		c : 頂点
	戻り値
		三角形の面積の2倍
		縮退しているときは 0
	制約
		なし
	計算量
		O(1)
	備考
		2倍を返しているのは、座標値が整数のときにはこの値も整数になるから。
*/
template<class T>
T area2(const point<T> &a, const point<T> &b, const point<T> &c ){
	return abs(cross(b-a,c-a));
}
/*
	三角形の面積(Heron)

	説明
		三辺の長さで定まる三角形の面積を求める
	引数
		a : 一辺の長さ
		b : 一辺の長さ
		c : 一辺の長さ
	戻り値
		三角形の面積
		三角形が作れないとき、縮退しているときには 0
	制約
		a>=0, b>=0, c>=0
		a<b+c, b<c+a, c<a+b(三角形の成立条件)
	計算量
		O(1)
	備考
		三角形が縮退しているときは nan を返すかもしれない
*/
double area(double a, double b, double c ){
	return sqrt((a+b-c)*(b+c-a)*(c+a-b)*(a+b-c))/4.;
}

/*
	多角形の面積

	説明
		多角形の面積(2倍)を求める
	引数
		G : 多角形
	戻り値
		三角形の面積の2倍
		縮退しているときは 0
	制約
		G は単純
	計算量
		O(n)
	備考
		2倍を返しているのは、座標値が整数のときにはこの値も整数になるから。
		多角形は CCW でも CW でもよい

		Verified: AOJ 0079 Area of Polygon
*/
template<class T>
T area2(const polygon<T> &G ){
	int n = G.size();
	T a = 0;
	rep (i, n ) a+=cross(G[i], G[(i+1)%n] );
	return abs (a );
}

/*
	二円の共通部分の面積を求める
*/

/*
	回転方向

	説明
		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;
}

/*
	反時計回りに変換

	説明
		多角形の頂点の順番が CW であれば CCW に変換する
		元々 CCW であれば何もしない
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		G : 多角形
	戻り値
		なし(引数 G が更新される)
	制約
		G は単純
	計算量
		O(n)
	備考
		単純多角形とは自己交差しない多角形のこと
		Verified: AOJ 0035 Is it Convex?
*/
// (A)
template<class T>
void to_ccw(polygon<T> &G ){
	int n = G.size();
	T A = 0;
	rep (i, n ) A+=cross(G[i], G[(i+1)%n] );
	if (A < 0 ) reverse (ALL (G ) );
}

// (B)
void to_ccw(polygon<double> &G ){
	int n = G.size();
	double A = 0.;
	rep (i, n ) A+=cross(G[i], G[(i+1)%n] );
	if (A<-EPS ) reverse (ALL (G ) );
}

/*
	点と点の距離

	説明
		点と点の距離を求める
		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 : 距離の二乗
	引数
		L : 直線
		p : 点
	戻り値
		直線 L と点 p の距離
	制約
		なし
	計算量
		O(1)
	備考

*/
template<class T>
double dist(const line<T> &L, const point<T> &p ){
	return abs (cross (L.b-L.a, p-L.a))/dist(L.a, L.b );
}

/*
	線分と点の距離

	説明
		線分と点の距離を求める
		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 );
}

/*
	線分と線分の距離
*/

/*
	三角形と点の包含判定

	説明
		三角形 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 ) );
}

/*
	直線と点の包含判定
*/

/*
	線分と点の包含判定

	説明
		線分が点を含むかどうかを判定する
		(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;
}

/*
	多角形と点の包含判定

	説明
		多角形が点を含むかどうかを判定する
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		G : 多角形
		p : 点
	戻り値
		含むなら true, 含まないなら false
	制約
		G は単純
	計算量
		O(n)
	備考
		G は凸でなくてもいい。
		点が多角形の境界にあるときは含むと判定する。
*/
// (A)
template<class T>
bool cover(const polygon<T> &G, const point<T> &p ){
	int n=G.size();
	bool in=false;
	rep(i,n){
		point<T> v1=G[i]-p, v2=G[(i+1)%n]-p;
		if(v1.y>v2.y) swap(v1,v2);
		// y 座標が小さい方の端点は含め、大きい方は含めない
		if(v1.y<=0 && 0<v2.y && cross(v1,v2)>0 ) in=!in;
		// p が辺 G[i]-G[i+1] 上にある
		if(cross(v1,v2)==0 && dot(v1,v2)<=0 ) return true;
	} // end rep
	return in;
}

// (B)
bool cover(const polygon<double> &G, const point<double> &p ){
	int n=G.size();
	bool in=false;
	rep(i,n){
		point<double> v1=G[i]-p, v2=G[(i+1)%n]-p;
		if(v1.y>v2.y) swap(v1,v2);
		// y 座標が小さい方の端点は含め、大きい方は含めない
		if(v1.y<EPS && EPS<v2.y && cross(v1,v2)>EPS ) in=!in;
		// p が辺 G[i]-G[i+1] 上にある
		if(abs(cross(v1,v2))<EPS && dot(v1,v2)<EPS ) return true;
	} // end rep
	return in;
}

/*
	多角形と多角形の包含判定
*/

/*
	円と点の包含判定

	説明
		円が点を含むかどうかを判定する
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		C : 円
		p : 点
	戻り値
		含むなら true, 含まないなら false
	制約
		なし
	計算量
		O(1)
	備考
*/
// (A)
template<class T>
bool cover (const circle<T> &C, const point<T> &p ){
	return dist2(C.c, p) <= C.r*C.r;
}

// (B)
bool cover (const circle<double> &C, const point<double> &p ){
	return dist (C.c, p ) < C.r + EPS;
}

/*
	円と線分の包含関係

*/
// (A)
template<class T>
bool intersect(const circle<T> &C, const segment<T> &S ){
	return dist2(S, C.c ) < C.r*C.r;
}
// (B)
bool intersect(const circle<double> &C, const segment<double> &S ){
	return dist(S, C.c ) < C.r + EPS;
}

/*
	直線と直線の交差判定
*/

/*
	直線と線分の交差判定
*/

/*
	線分と線分の交差判定

	説明
		線分と線分が交わるかどうかを判定する
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		S1 : 線分
		S2 : 線分
	戻り値
		交わるなら true, 交わらないなら false
	制約
		なし
	計算量
		O(1)
	備考
		bounding box によるラフチェックは必要。( ccw による判定だと、二線分が同一直線上にあるとき間違う。)

		Verified: AOJ 2003 Railroad Conflict
*/
// (A)
template<class T>
bool intersect(const segment<T> &S1, const segment<T> &S2 ){
	if (max (S1.a.x, S1.b.x ) < min (S2.a.x, S2.b.x )
	|| max (S1.a.y, S1.b.y ) < min (S2.a.y, S2.b.y )
	|| max (S2.a.x, S2.b.x ) < min (S1.a.x, S1.b.x )
	|| max (S2.a.y, S2.b.y ) < min (S1.a.y, S1.b.y ) ) return false;
	return ccw (S1.a, S1.b, S2.a )*ccw (S1.a, S1.b, S2.b ) <= 0
		&& ccw (S2.a, S2.b, S1.a )*ccw (S2.a, S2.b, S1.b ) <= 0;
}
// (B)
bool intersect(const segment<double> &S1, const segment<double> &S2 ){
	if (max (S1.a.x, S1.b.x )+EPS < min (S2.a.x, S2.b.x )
	|| max (S1.a.y, S1.b.y )+EPS < min (S2.a.y, S2.b.y )
	|| max (S2.a.x, S2.b.x )+EPS < min (S1.a.x, S1.b.x )
	|| max (S2.a.y, S2.b.y )+EPS < min (S1.a.y, S1.b.y ) ) return false;
	return ccw (S1.a, S1.b, S2.a )*ccw (S1.a, S1.b, S2.b ) <= 0
		&& ccw (S2.a, S2.b, S1.a )*ccw (S2.a, S2.b, S1.b ) <= 0;
}

/*
	多角形と線分の交差判定

	説明
		多角形と線分が交わるかどうかを判定する
	引数
		G : 多角形
		S : 線分
	戻り値
		交わるなら true, 交わらないなら false
	制約
		なし
	計算量
		O(n)
	備考
		G は凸でなくていい。
		G は境界を含む
		S が G の内部にあるときは交わると判定する
*/
template<class T>
bool intersect(const polygon<T> &G, const segment<T> &S ){
	int n = G.size();
	if (cover(G, S.a ) || cover (G, S.b ) ) return true;
	rep (i, n ) if (intersect((segment<T>){G[i], G[(i+1)%n]}, S ) ) return true;
	return false;
}

/*
	多角形と多角形の交差判定
*/

/*
	円と直線の交差判定

	説明
		円と直線が交わるかどうかを判定する
	引数	
		C: 円
		L: 直線
	戻り値
		交点の個数
	制約
		なし
	計算量
		O(1)
	備考
		
*/
int intersect(const circle<double> &C, const line<double> &L ){
	point<double> m=proj(C.c, L );
	double d = abs (C.c - m );
	if (C.r + EPS < d ) return 0;
	if (C.r - EPS < d ) return 1;
	return 2;
}

/*
	二直線の交点

	説明
		二直線の交点を求める
		(A)(直線を特徴付ける点の)座標値が整数
		(B)(直線を特徴付ける点の)座標値が実数
	引数
		L1 : 直線
		L2 : 直線
	戻り値
		L1 と L2 の交点
	制約
		二直線は交点を持つこと。(平行でない or L1 == L2 )
	計算量
		O(1)
	備考
		交点が複数あるとき(L1 == L2)は L1.a を返す。
		この仕様は線分 S と直線 L の交点を求めたいとき重要。
		( S と L が同一直線上にあるときにも、S を第1引数に指定することで交点が正しく求まる。)
*/
// (A)
template<class T>
point<double> get_intersect(const line<T> &L1, const line<T> &L2 ){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if (a1==0) return L1.a;	// L1 == L2
	return (point<double>)L2.a+a2/a1*(point<double>)(L2.b-L2.a);
}
// (B)
point<double> get_intersect(const line<double> &L1, const line<double> &L2 ){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if (abs(a1)<EPS) return L1.a;	// L1 == L2
	return L2.a+a2/a1*(L2.b-L2.a);
}

/*
	線分と線分の交点

	説明
		線分と線分の交点を求める
		(A)(線分を特徴付ける点の)座標値が整数
		(B)(線分を特徴付ける点の)座標値が実数
	引数
		S1 : 線分
		S2 : 線分
	戻り値
		S1 と S2 の交点
	制約
		二線分は交点を持つこと( intersect(segment, segment ) で判定できる)
	計算量
		O(1)
	備考
		Verified: AOJ 2003 Railroad Conflict
*/
// (A)
// todo
// (B)
point<double> get_intersect(const segment<double> &S1, const segment<double> &S2 ){
	double a1=cross(S1.b-S1.a,S2.b-S2.a);
	double a2=cross(S1.b-S1.a,S1.b-S2.a);
	if (abs(a1)<EPS){
		if(cover(S1,S2.a) ) return S2.a;
		if(cover(S1,S2.b) ) return S2.b;
		if(cover(S2,S1.a) ) return S1.a;
		return S1.b;
	} // end if
	return S2.a+a2/a1*(S2.b-S2.a);
}

/*
	円と直線の交点

	説明
		円と直線の交点を求める
	引数
		C : 円
		L : 直線
		res : 計算結果(交点の集合)
	戻り値
		交点の個数
	制約
		なし
	計算量
		O(1)
	備考
		res は初期化されない
*/
int get_intersect(const circle<double> &C, const line<double> &L, vector< point<double> > &res ){
	point<double> h=proj(C.c,L);
	double d=dist(C.c,h);
	if (d>C.r+EPS) return 0;
	if (d>C.r-EPS){
		res.push_back (h );
		return 1;
	}else{
		point<double> v=L.b-L.a;
		v=(sqrt(C.r*C.r-d*d)/abs(v))*v;
		res.push_back (h+v);
		res.push_back (h-v);
		return 2;
	} // end if
}

/*
	円と円の交点

	説明
		円と円の交点を求める
	引数
		C1 : 円
		C2 : 円
		res : 計算結果(交点の集合)
	戻り値
		交点の個数
		ただし、交点が無限個になる(2つの円が等しい)ときは -1
	制約
		なし
	計算量
		O(1)
	備考
		res は初期化されない
		交点が無限個あるときは res には何も追加されない
		Verified:
			AOJ 0090 Overlaps of Seals
			AOJ 1132 Circle and Points					
*/
int get_intersect(const circle<double> &C1, const circle<double> &C2, vector< point<double> > &res ){
	double r1=C1.r,r2=C2.r;
	point<double> p1=C1.c,p2=C2.c;

	double d=abs(p1-p2);
	if (d<EPS && abs(r1-r2)<EPS ){	// C1 == C2
		return -1;
	}else
	if (r1+r2<d-EPS || d+EPS<abs(r1-r2) ){
		return 0;
	}else{
		double a = (r1*r1-r2*r2+d*d)/(2.*d);
		double h = sqrt(max(r1*r1-a*a, 0. ) );
		point<double> tmp1 = p1+a/d*(p2-p1);
		point<double> tmp2 = h/d*(p2-p1);
		if (abs(tmp2)<EPS ){
			res.push_back (tmp1 );
			return 1;
		}else{
			res.push_back ((point<double>){tmp1.x-tmp2.y, tmp1.y+tmp2.x});
			res.push_back ((point<double>){tmp1.x+tmp2.y, tmp1.y-tmp2.x});
			return 2;
		} // end if
	} // end if
}

/*
	点から円に引いた接線の交点
*/

/*
	円と円の共通接線

	説明
		円と円の共通接線を求める
	引数
		C1 : 円
		C2 : 円
		res : 計算結果(接線の場合)
	戻り値
		接線の本数
	計算量
		O(1)
	備考
		res は初期化されない
		Verified: AOJ 	2201 Immortal jewels
*/
int tangent(const circle<double> &C1, const circle<double> &C2, vector< line<double> > &res ){
	double d=abs(C1.c-C2.c);
	if (d<EPS ) return 0;	// C1,C2 は同心円上にある

	int c = 0;
	// 内接線
	if(C1.r+C2.r<d-EPS ){
		double t=acos((C1.r+C2.r)/d);
		res.push_back((line<double>){C1.c+rot(C1.r/d*(C2.c-C1.c), t),C2.c+rot(C2.r/d*(C1.c-C2.c), t)});
		res.push_back((line<double>){C1.c+rot(C1.r/d*(C2.c-C1.c),-t),C2.c+rot(C2.r/d*(C1.c-C2.c),-t)});
		c+=2;
	}else
	if (C1.r+C2.r<d+EPS ){
		point<double> p=C1.c+C2.r/d*(C2.c-C1.c);
		res.push_back ((line<double>){p,p+rot(C2.c-C1.c,PI/2)});
		c++;
	} // end if
	
	// 外接線
	if (abs(C1.r-C2.r)<d-EPS ){
		double t1=acos((C1.r-C2.r)/d),t2=PI-t1;
		res.push_back((line<double>){C1.c+rot(C1.r/d*(C2.c-C1.c), t1),C2.c+rot(C2.r/d*(C1.c-C2.c),-t2)});
		res.push_back((line<double>){C1.c+rot(C1.r/d*(C2.c-C1.c),-t1),C2.c+rot(C2.r/d*(C1.c-C2.c), t2)});
		c+=2;
	}else
	if (abs(C1.r-C2.r)<d+EPS ){
		point<double> p=C1.c+C1.r/d*(C2.c-C1.c);
		res.push_back((line<double>){p,p+rot(C2.c-C1.c,PI/2)});
		c++;
	} // end if
	
	return c;
}
/*
	垂直二等分線

	説明
		二点 a, b の垂直二等分線を求める
	引数
		a : 点
		b : 点
	戻り値
		a と b の垂直二等分線
	計算量
		O(1)
	備考
		垂直二等分線を L とすると、L.a から L.b の方向を見たとき、左手に点 a が来る。
		AOJ 0081 A_Symmetric_Point では上手く動かなかった。

*/
template<class T>
line<double> perp_bisector(const point<T> &a, const point<T> &b ){
	return (line<double>){(point<double>){(a.x-a.y+b.x+b.y)/2.0, (a.y+a.x+b.y-b.x)/2.0 },
							(point<double>){(a.x+a.y+b.x-b.y)/2.0, (a.y-a.x+b.y+b.x)/2.0 }};
}

/*
	点対称

	説明
		点 b を基準に点 a を点対称を求める
	引数
		a : 点
		b : 点
	戻り値
		点対称の点
	計算量
		O(1)
	備考

*/
template<class T>
point<T> symmetry_point (const point<T> a, const point<T> b )
{
	return (point<T>){2*b.x-a.x, 2*b.y-a.y};
}

/*
	多角形の重心の座標

	説明
		頂点数 n の凸多角形をひとつの頂点を基準に n - 2 個の三角形に分割した三角形の面積を Sk,
		重心を gk とおくと n の凸多角形の重心 G は

		G = \sum_{k=1}^{n-2}Sk*gk/(\sum_{k=1}^{n-2}Sk)

		で求められる。
	引数
		G : 多角形
	戻り値
		点
	計算量
		O(n)
	備考
		Verified: AOJ 2442 ConvexCut しかし EPS=1e-6 にしないと WA.
*/
template<class T>
point<T> centerG(const polygon<T> &G ){
	int n = G.size();
	double S = 0.;
	point<double> g; g.x = 0.; g.y = 0.;
	int u = G.size()-1;
	for (int i = 0; i < n; u=i++ ){
		double sk = cross (G[u], G[i] );
		S += sk;
		g.x += (G[u].x + G[i].x)*sk;
		g.y += (G[u].y + G[i].y)*sk;
	} // end for
	g /= (3.*S);

	return g;
}
/*
	多角形の重心まわりの反時計回りに並び替える
	
	説明
		原点まわりの反時計回りに並び替える
	引数
		G : 多角形
	戻り値
		なし(引数を返すから。)
	計算量
		O(n*log n)
	備考
		
*/
typedef pair<pair<double,double>, int> DDI;

bool cmp (DDI a, DDI b ){
	if (a.first.first != b.first.first ){
		return a.first.first < b.first.first;
	} // end if
	return a.first.second > b.first.second;
}
template<class T>
void to_ccw2 (polygon<T> &G ){
	int n = G.size();
	point<T> g = centerG(G );
	vector<DDI> order (n );
	rep (i, n ){
		order[i].first.first = arg(G[i]-g );
		order[i].first.second = abs (G[i]-g );
		order[i].second = i;
	} // end rep
	sort (ALL (order ), cmp );
	polygon<T> res (n );
	rep (i, n ) res[i] = G[order[i].second];

	G=res;
}
/*
	二点と半径で定まる円
*/

/*
	凸性判定
	
	説明
		多角形が凸かどうかを判定する
	引数
		G : 多角形
	戻り値
		G は単調かつ頂点の順番が CCW で与えられていること
	計算量
		O(n)
	備考
		Verified: AOJ 0035 Is it Convex
*/
template<class T>
bool is_convex(const polygon<T> &G ){
	int n = G.size();
	rep (i, n ) if (ccw (G[i], G[(i+1)%n], G[(i+2)%n])== CW ) return false;
	return true;
}

/*
	凸包

	説明
		点集合の凸包を求める
	引数
		P : 点集合
	戻り値
		P の凸包
	制約
		なし
	計算量
		O(n log n )
	備考
		P は破壊される。

		sort は (x, y ) の辞書順。

		凸包の同じ直線上にある頂点は端のものだけを拾う。
		辺上になる頂点を全部拾うようにしたいときは != CCW を ==CW と修正すればよい。

		Verified: AOJ 0068 Enclose Pins with a Rubber Band
		(この場合は辺上の頂点も拾いたかったので ==CW とした。)

*/
template<class T>
polygon<T> convex_hull(vector< point<T> > &P ){
	int n = P.size();
	polygon<T> CH;
	if (n <= 1 ){
		CH.insert (CH.end(), P.begin(), P.end() );
		return CH;
	} // end if
	sort (ALL (P ) );
	rep (cnt, 2 ){
		int m = 0;
		vector< point<T> > half(n );
		rep (i, n ){
			half[m++] = P[i];
			while (m >= 3 && ccw (half[m-3], half[m-2], half[m-1] ) != CCW ){
				half[m-2] = half[m-1];
				m--;
			} // end while
		} // end rep
		CH.insert (CH.end(), half.begin(), half.begin()+m-1 );
		reverse (ALL (P ) );
	} // end rep
	
	return CH;
}

/*
	凸多角形の切断

	凸多角形と半平面の交差

	説明
		凸多角形と半平面の共通部分を求める
	引数
		G : 凸多角形
		L : 直線
	戻り値
		G と L の左側の半平面の共通部分
	制約
		なし
	計算量
		O(n)
	備考
		半平面は L.a から L.b へ向いたときの左側の部分として指定されている。
		共通部分は凸多角形になる。(凸集合の全体は intersection について閉じている。)
		L 上に G の点 p があっても、出力される多角形には p が一度だけ表れる。

*/
template<class T>
polygon<double> convex_cut(const polygon<T> &G, const line<T> &L ){
	int n=G.size();
	polygon<double> H; H.clear();
	rep (i, n ){
		int d1=ccw(L.a,L.b,G[i] );
		int d2=ccw(L.a,L.b,G[(i+1)%n] );
		if (d1!=CW )H.push_back(G[i] );
		if (d1==CCW && d2==CW || d1==CW && d2==CCW ){
			H.push_back (get_intersect(L,(line<T>){G[i],G[(i+1)%n]}));
		} // end if
	} // end rep

	return H;
}
/*
	内接円の半径

	説明
		辺長がそれぞれ、a, b, c である三角形の内接円の半径を求める
	引数
		a: 辺長
		b: 辺長
		c: 辺長
	戻り値
		内接円の半径
	制約
		a >= 0, b >= 0, c >= 0
		a < b + c, c < c + a, c < a + b (三角形の成立条件)
	計算量
		O(1)
	備考
		三角形が縮退しているときは nan を返すかもしれない
*/
double inradius(double a, double b, double c ){
	return sqrt ((b+c-a)*(c+a-b)*(a+b-c)/(a+b+c))/2.;
}

/*
	外接円

	説明
		三角形 abc の外接円を求める
	引数
		a: 頂点
		b: 頂点
		c: 頂点
	戻り値
		外接円
	制約
		a, b, c は同一直線上にないこと
	計算量
		O(1)
	備考
		a, b, c が同一直線上にあるときは外接円は存在しない
		頂点が整数座標のとき、外心の座標と半径の二乗は有理数となる

		Verified: AOJ 0010 Circumscribed Circle of a Triangle

*/
circle<double> circumcircle(const point<double> &a, point<double> b, point<double> c ){
	b-=a; c-=a;
	double A2 = abs2(b-c), B2 = abs2(b), C2 = abs2(c);
	double d = 2*cross(b,c);
	double nx = c.y*B2-b.y*C2;
	double ny = b.x*C2-c.x*B2;
	double r2 = A2*B2*C2/(d*d);
	return (circle<double>){a+(point<double>){nx/d, ny/d}, sqrt(r2)};
}

/*
	外接円の半径
	
	説明
		辺長がそれぞれ a, b, c である三角形の外接円の半径を求める
	引数
		a : 辺長
		b : 辺長
		c : 辺長
	戻り値
		外接円の半径
	制約
		a >= 0, b >= 0, c >= 0
		a < b + c, b < c + a, c < a + b (三角形の成立条件)
	計算量
		O(1)
	備考
		三角形が縮退しているときは nan を返すかもしれない

		Verified: AOJ 0010 Circumscribed Circle of a Triangle

*/
double circumradius(double a, double b, double c ){
	return a*b*c/sqrt((a+b+c)*(b+c-a)*(c+a-b)*(a+b-c) );
}

/*
	最小包含球

	説明
		点集合の包含する半径最小の DIM 次元球を求める Welzl のアルゴリズム
	引数
		n : 点集合のサイズ
		P : 点集合
	戻り値
		P に対する最小包含球
	制約
		なし
	計算量
		DIM を定数とみたとき
		平均 : O(n)
		最悪 : O(n^(DIM+1))
	備考
		コードは DIM = 2 のときを想定している。
		DIM = 3 のときは
		- すべての circle を sphere に
		- すべての point を point3 に
		置き換えればよい。
		
		P は破壊される

		スタックオーバーフローに注意。

		P のすべての点の座標が有理数のとき、最小包含球の中心、半径の二乗は共に有理数になる。
		コードを少し書き直す必要があるけど、誤差がこわいときは試してみるといい。

		原論文は Welzl Emo "Smallest enclosing disks (balls and ellipsoilds)".

		move-to-front heurictic を入れればさらに速くなるけど、すでに十分速いので必要ない。
		実装は Spaghetti Source をかなり参考にした。

*/
class smallest_enclosing_ball{
	static const int DIM=2;
	
	// 与えられた点集合
	int n;
	point<double> *P;

	// 境界にある点集合
	int n_bd;
	point<double> bd[DIM+1];
	
	// {bd[0], ..., db[n_bd-1]} の最小包含球を求める
	circle<double> naive(){
		if (n_bd == 0 ) return (circle<double>){(point<double>){0,0},-1};

		// Gram-Schmidt で使う作業
		point<double> v[DIM];		// v[i]:=( v[0], ..., v[i-1] と直交するベクトル )
		double z[DIM]; 			// z[i]:=|v[i]|^2
	
		// (cen, sqrt(R2)):=({bd[0], ..., bd[i]} の最小包含球 )
		point<double> cen=bd[0];
		double R2=0;
		rep(i,n_bd-1){
			point<double> delta=bd[i+1]-cen;
			
			// Gram-Schmidt
			v[i]=delta;
			rep(j,i){
				v[i]=dot(v[j],delta)/z[j]*v[j];
			} // end rep
			z[i]=dot(v[i],v[i]);
		
			double mag=abs2(delta)-R2;
			cen+=mag/(2*z[i])*v[i];
			R2+=mag*mag/(4*z[i]);
		} // end rep

		return (circle<double>){cen,sqrt(R2)};
	}

	circle<double> dfs(int i ){
		if(i==n || n_bd==DIM+1) return naive();

		// P[i] を境界として使わない場合
		circle<double> C=dfs(i+1);
		// P[i] を境界として使う場合
		if(C.r==-1||!cover(C,P[i])){
			bd[n_bd++]=P[i];
			C=dfs(i+1);
			n_bd--;
		} // end if
		
		return C;
	}
public:
	circle<double> solve(int n, point<double> *P){
		this->n=n;
		this->P=P;
		random_shuffle(P,P+n);
		n_bd=0;
		return dfs(0);
	}
};

/*
	線分アレンジメント
*/

/*
	最近点対

	説明
		最近点対問題を解く
	引数
		n : 点の個数
		p : 点集合
	戻り値
		最近点対の距離
	制約
		n>=2
	計算量
		O(n log n)
	備考
		sort は (x,y) の辞書順。
		P の順番は破壊される(内部でソートするため)

		Verified: AOJ 2057 The Closest Circle
*/
struct cmp_y{
bool operator()(const point<double> &a, const point<double> &b ){
	return (a.y+EPS<b.y || (abs(a.y-b.y)<EPS && a.x+EPS<b.x ) );
}};

double closest_pair(int n, point<double> *P){
	sort (P, P+n );
	double d = dist(P[0],P[1] );
	set<point<double>, cmp_y> S;
	set<point<double>, cmp_y>::iterator it_l, it_r, it;
	for (int i = 0, j = 0; i < n; i++ ){
		it_l = S.lower_bound ((point<double>){0,P[i].y-d-1.});
		it_r = S.upper_bound ((point<double>){0,P[i].y+d+1.});
		for (it=it_l;it!=it_r;++it) d=min(d, dist(*it,P[i]));
		while(P[i].x-P[j].x>d+EPS ) S.erase(P[j++] );
		S.insert(P[i] );
	} // end for

	return d;
}

/*
	楕円の周長
*/

/*
	多角形の合同判定

	説明
		2つの多角形が合同かどうか(平行移動、回転、反転で一致するか)を判定する
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		G1 : 多角形
		G2 : 多角形
	戻り値
		G1 と G2 が合同なら true, 合同でないなら false
	制約
		G1, G2 は単純で、頂点の順番が CCW で与えられていること
	計算量
		O(n^2) (n==n1==n2)
	備考
		頂点が一対一に対応するかどうかを判定するので
			G1 = {(0,0)}
			G2 = {(0,0),(0,0)}
		や
			G1 = {(0.0),(2,0),(0,1)}
			G2 = {(0,0),(1,0),(2,0),(0,1)}
		については false を返す
*/
// (A)
template<class T>
bool is_congruent(polygon<T> G1, polygon<T> G2 ){
	int n1=G1.size(), n2=G2.size();
	if(n1!=n2) return false;
	if(n1==1) return true;
	rep (cnt, 2 ){
		// 辺 G1[0]-G1[1] と 辺 G2[i]-G2[(i+1)%n2] を対応させる
		rep (i, n2 ){
			bool ok = true;
			rep (j, n2 ){
				point<int> v1=G1[1]-G1[0], v2=G2[(i+1)%n2]-G2[i];
				point<int> w1=G1[j]-G1[0], w2=G2[(i+j)%n2]-G2[i];
				if (dot(v1,w1) == dot(v2,w2)
				|| cross(v1,w1) == cross(v2,w2) ){ ok = false; break; }
			} // end rep
			if (ok ) return true;
		} // end rep
		// G2 を裏返す
		rep (i, n2 ) G2[i].x*=-1;
	} // end rep

	return false;
}	

//(B)
template<class T>
bool is_congruent(polygon<double> G1, polygon<double> G2 ){
	int n1=G1.size(), n2=G2.size();
	if(n1!=n2) return false;
	if(n1==1) return true;
	rep (cnt, 2 ){
		// 辺 G1[0]-G1[1] と 辺 G2[i]-G2[(i+1)%n2] を対応させる
		rep (i, n2 ){
			bool ok = true;
			rep (j, n2 ){
				point<int> v1=G1[1]-G1[0], v2=G2[(i+1)%n2]-G2[i];
				point<int> w1=G1[j]-G1[0], w2=G2[(i+j)%n2]-G2[i];
				if (abs(dot(v1,w1) - dot(v2,w2) ) > EPS
				|| abs(cross(v1,w1) - cross(v2,w2) ) > EPS ){ ok = false; break; }
			} // end rep
			if (ok ) return true;
		} // end rep
		// G2 を裏返す
		rep (i, n2 ) G2[i].x*=-1;
	} // end rep

	return false;
}
/*
	冗長な頂点の削除
*/

/*
	二点間の円の内部を通らない最短距離
*/

/*
	ボロノイ図

	説明
		k番目の点のボロノイ領域を求める
	引数
		g : 多角形(外枠)
		v : 点の集合
		k : 点の集合の中の k 番目の点	
	戻り値
		res : 多角形
	制約
		外枠が凸多角形でないときも動く?
		g は破壊される。
		(多角形の切断で g は書き換えられるため。)
	計算量
		O(n*(n+m))
	備考
	
*/
template<class T>
polygon<T> voronoi_cell(polygon<T> g, polygon<T> v, int k ){
	int n = v.size();
	rep (i, n ) if (i != k ) g = convex_cut (g, perp_bisector (v[k], v[i] ) );

	return g;
}
int main()
{
//	cut here before submit 
//	freopen ("testcase.C1-2", "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});
			int m = M.size();	// 監視所の数
			// 点が一致している?
			rep (tpos, 2 ){
				rep (j, m ){
					if (abs(M[j] - T[tpos] ) < EPS ){
						ok = false;
						break;
					} // end if
				} // end rep
				if (!ok ) break;
			} // end rep					

			// 線分上にある?
			rep (tpos, 2 ){
				rep (i, m ){
					for (int j = i+1; j < m; j++ ){
						if (cover ((segment<double>){M[i],M[j]},T[tpos]) ){
							ok = false;
							break;
						} // end if
					} // end for
					if (!ok ) break;
				} // end rep
				if (!ok ) break;					
			} // end rep

			// 凸多角形と2点の位置関係が一致している?
			if (m >= 3 ){
				vector< point<double> > tmp = M;
				polygon<double> g = convex_hull (tmp );  
				if (cover (g, T[0] ) != cover (g, T[1] ) ){
					ok = false;
				} // end if
			} // 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 35753 Byte
Status WA
Exec Time 5035 ms
Memory 948 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 × 49
WA × 1
AC × 73
WA × 1
TLE × 1
AC × 78
WA × 1
TLE × 21
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 21 ms 784 KB
11_rand01.txt AC 24 ms 788 KB
11_rand02.txt AC 23 ms 780 KB
11_rand03.txt AC 22 ms 788 KB
11_rand04.txt AC 22 ms 780 KB
11_rand05.txt AC 20 ms 780 KB
11_rand06.txt AC 21 ms 784 KB
11_rand07.txt AC 21 ms 776 KB
11_rand08.txt AC 18 ms 780 KB
11_rand09.txt AC 21 ms 780 KB
11_rand10.txt AC 22 ms 780 KB
11_rand11.txt AC 20 ms 732 KB
11_rand12.txt AC 22 ms 728 KB
11_rand13.txt AC 21 ms 776 KB
11_rand14.txt AC 21 ms 780 KB
11_rand15.txt AC 21 ms 780 KB
11_rand16.txt WA 23 ms 752 KB
11_rand17.txt AC 19 ms 780 KB
11_rand18.txt AC 20 ms 776 KB
11_rand19.txt AC 21 ms 704 KB
11_rand20.txt AC 21 ms 780 KB
11_rand21.txt AC 21 ms 780 KB
11_rand22.txt AC 21 ms 788 KB
11_rand23.txt AC 20 ms 780 KB
11_rand24.txt AC 22 ms 772 KB
21_rand00.txt AC 21 ms 788 KB
21_rand01.txt AC 21 ms 780 KB
21_rand02.txt AC 24 ms 784 KB
21_rand03.txt AC 24 ms 784 KB
21_rand04.txt AC 21 ms 780 KB
21_rand05.txt AC 21 ms 784 KB
21_rand06.txt AC 27 ms 780 KB
21_rand07.txt AC 25 ms 784 KB
21_rand08.txt AC 24 ms 780 KB
21_rand09.txt AC 21 ms 780 KB
21_rand10.txt AC 21 ms 784 KB
21_rand11.txt AC 21 ms 784 KB
21_rand12.txt AC 21 ms 780 KB
21_rand13.txt AC 19 ms 780 KB
21_rand14.txt AC 26 ms 780 KB
21_rand15.txt AC 24 ms 784 KB
21_rand16.txt AC 24 ms 788 KB
21_rand17.txt AC 23 ms 776 KB
21_rand18.txt AC 21 ms 788 KB
21_rand19.txt AC 21 ms 784 KB
21_rand20.txt AC 26 ms 780 KB
21_rand21.txt AC 21 ms 784 KB
21_rand22.txt AC 20 ms 776 KB
21_rand23.txt AC 18 ms 772 KB
21_rand24.txt AC 20 ms 784 KB
31_rand00.txt AC 64 ms 780 KB
31_rand01.txt AC 2369 ms 788 KB
31_rand02.txt AC 1407 ms 780 KB
31_rand03.txt AC 2393 ms 780 KB
31_rand04.txt AC 124 ms 784 KB
31_rand05.txt TLE 5029 ms 788 KB
31_rand06.txt AC 1393 ms 780 KB
31_rand07.txt AC 575 ms 780 KB
31_rand08.txt AC 2696 ms 784 KB
31_rand09.txt AC 2196 ms 776 KB
31_rand10.txt AC 93 ms 780 KB
31_rand11.txt AC 44 ms 776 KB
31_rand12.txt AC 1949 ms 776 KB
31_rand13.txt AC 3196 ms 784 KB
31_rand14.txt AC 23 ms 784 KB
31_rand15.txt AC 2073 ms 776 KB
31_rand16.txt AC 2005 ms 780 KB
31_rand17.txt AC 196 ms 780 KB
31_rand18.txt AC 280 ms 712 KB
31_rand19.txt AC 1753 ms 780 KB
31_rand20.txt AC 344 ms 780 KB
31_rand21.txt AC 231 ms 780 KB
31_rand22.txt AC 2166 ms 776 KB
31_rand23.txt AC 2266 ms 780 KB
31_rand24.txt AC 1947 ms 772 KB
41_rand00.txt TLE 5030 ms 828 KB
41_rand01.txt TLE 5035 ms 784 KB
41_rand02.txt TLE 5029 ms 828 KB
41_rand03.txt TLE 5031 ms 908 KB
41_rand04.txt TLE 5030 ms 832 KB
41_rand05.txt TLE 5034 ms 948 KB
41_rand06.txt TLE 5031 ms 780 KB
41_rand07.txt TLE 5029 ms 880 KB
41_rand08.txt TLE 5028 ms 824 KB
41_rand09.txt TLE 5030 ms 864 KB
41_rand10.txt TLE 5030 ms 780 KB
41_rand11.txt TLE 5028 ms 816 KB
41_rand12.txt TLE 5031 ms 780 KB
41_rand13.txt TLE 5033 ms 724 KB
41_rand14.txt TLE 5030 ms 904 KB
41_rand15.txt TLE 5031 ms 836 KB
41_rand16.txt TLE 5030 ms 780 KB
41_rand17.txt TLE 5028 ms 912 KB
41_rand18.txt AC 38 ms 784 KB
41_rand19.txt AC 348 ms 776 KB
41_rand20.txt AC 76 ms 740 KB
41_rand21.txt AC 83 ms 780 KB
41_rand22.txt AC 66 ms 780 KB
41_rand23.txt TLE 5032 ms 800 KB
41_rand24.txt TLE 5031 ms 928 KB