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