Submission #1192557


Source Code Expand

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define sz size()
#define all(a) (a).begin(),(a).end()

using namespace std;
typedef long double D;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< vector<pii> > graph;

const D EPS = 1e-8;
const D Eps = 1e-6;
const D PI = acos(-1);
inline bool EQ(const D a, const D b){ return abs(a-b)<EPS; }

//for angle
inline D deg_add(D d, D a){
  D res = d + a;
  while(res >= 2*PI) res -= 2*PI;
  while(res < 0) res += 2*PI;
  return res;
}

inline bool in_angle(D d, D l, D r){
  if(l < r) return l+EPS<d and d+EPS<r;
  if(l < d+EPS) return l+EPS<d and d+EPS<r+2*PI;
  return l-2*PI+EPS<d and d+EPS<r;
}

//Point class
struct P{
  D x,y;
  P(D a=0, D b=0):x(a),y(b){}

  inline P operator-()const{ return P(-x,-y); }
  inline P operator+(const P a)const{ return P(x+a.x,y+a.y); }
  inline P operator-(const P a)const{ return P(x-a.x,y-a.y); }
  inline P operator*(const P a)const{ return P(x*a.x-y*a.y, x*a.y+y*a.x); }
  inline P operator*(const D a)const{ return P(x*a,y*a); }
  inline P operator/(const D a)const{ return P(x/a,y/a); }
  
  inline P operator+=(const P a){ return P(x+=a.x,y+=a.y); }
  inline P operator-=(const P a){ return P(x-=a.x,y-=a.y); }
  inline P operator*=(const D a){ return P(x*=a,y*=a); }
  inline P operator/=(const D a){ return P(x/=a,y/=a); }

  inline bool operator==(const P a)const{ return EQ(x,a.x) && EQ(y,a.y); }
  inline bool operator!=(const P a)const{ return !(*this==a); }
  inline bool operator<(const P a)const{ return EQ(x,a.x)?y<a.y:x<a.x; }
  inline bool operator<=(const P a)const{ return *this<a || *this==a; }
  inline bool operator>(const P a)const{ return !(*this<=a); }
  inline bool operator>=(const P a)const{ return !(*this<a); }
};

inline D dot(const P a, const P b){ return a.x*b.x + a.y*b.y; }
inline D cross(const P a, const P b){ return a.x*b.y - a.y*b.x; }

inline D norm(const P a){ return a.x*a.x + a.y*a.y; }
inline D abs(const P a){ return sqrt(norm(a)); }

inline P unit(const P a){ return a/abs(a); }
inline pair<P,P> normal(const P a){ return make_pair(a*P(0,1),a*P(0,-1)); }

inline D arg(const P a){
  D s = atan2(a.y,a.x);
  while(s < 0) s += 2*PI;
  while(s >= 2*PI) s -= 2*PI;
  return s;
}

//rotate a point counter-clockwise on the origin
inline P rotate(const P a, const D s){ return a * P(cos(s),sin(s)); }

//return seta A
inline D arg(P a,P b,P c){
  D s = acos(dot(b-a,c-a)/(abs(b-a)*abs(c-a)));
  while(s < 0) s += 2*PI;
  while(s >= 2*PI) s -= 2*PI;
  return s;
}
inline D arg(D a,D b,D c){
  D s = acos( (b*b+c*c-a*a)/(2*b*c) );
  while(s < 0) s += 2*PI;
  while(s >= 2*PI) s -= 2*PI;
  return s;
}

inline int ccw(const P a,P b,P c){
  b -= a;c -= a;
  if(cross(b,c)>EPS) return 1;      //counter clockwise
  if(cross(b,c)<-EPS) return -1;    //clockwise
  if(dot(b,c)<EPS) return 2;       //c--a--b on line
  if(abs(b)<abs(c)+EPS) return -2;  //a--b--c on line
  return 0;                         //on segment
}

//Line (or Segment) class
struct L{
  P s,t;
  L(const P a=P(0,0), const P b=P(0,1)):s(a),t(b){}
};

inline bool para(L a,L b){return abs(cross(a.s-a.t,b.s-b.t))<EPS;}

inline bool is_cp(L a,L b){
  if(ccw(a.s,a.t,b.s)*ccw(a.s,a.t,b.t)<=0)
    if(ccw(b.s,b.t,a.s)*ccw(b.s,b.t,a.t)<=0)return true;
  return false;
}

inline P line_cp(L a,L b){
  return a.s+(a.t-a.s)*cross(b.t-b.s,b.s-a.s)/cross(b.t-b.s,a.t-a.s);
}

typedef vector<P> Poly;

inline void print(Poly p){
  cout << "[";
  for(P x : p) cout << "(" << x.x << ", " << x.y << "), ";
  cout << "]" << endl;
}

//all vertex is already sorted.
inline D area(Poly p){
  if(p.size()<3)return 0;
  D res = cross(p[p.sz-1],p[0]);
  rep(i,p.sz-1)res += cross(p[i],p[i+1]);
  return res/2;
}

//convex, vertexes are in the counter-clockwise order.
inline bool in_poly(const Poly p,const P x){
  if(p.size() <= 2) return false;
  rep(i,p.size()){
    P a = p[i], b = p[(i+1)%p.size()];
    if(ccw(a,b,x) != 1) return false;
  }
  return true;
}

struct C{
  P c; D r;
  C(P _c, D _r):c(_c), r(_r) {}
};

inline vector<P> cir_cir_cp(C a, C b){
  vector<P> res;

  D dis = abs(a.c - b.c);
  if(dis > a.r + b.r + EPS) return res;

  P x = unit(b.c - a.c) * a.r;
  if( EQ(dis, a.r+b.r) ){
    res.pb(a.c + x);
  }else{
    D s = arg(b.r, abs(b.c-a.c), a.r);
    res.pb(a.c + rotate(x,s));
    res.pb(a.c + rotate(x,-s));
  }
  return res;
}

inline vector<P> cir_line_cp(C a, L l){
  vector<P> res;
  P n = normal(l.s-l.t).first;
  P p = line_cp(l, L(a.c,a.c+n));
  D dis = abs(p-a.c); 
  if( EQ(dis, a.r) ) res.pb(p);
  else if(dis < a.r){
    D len = sqrt(a.r*a.r - dis*dis);
    P cp_vec = unit(l.s-l.t)*len;
    res.pb(p + cp_vec);
    res.pb(p - cp_vec);
  }
  return res;
}

struct Fin{
  P c;
  D r, d1, d2;
  Fin(P _c, D _r, D _d1, D _d2):c(_c), r(_r), d1(_d1), d2(_d2) {}
};

inline bool in_fin(Fin f, P x){
  D s = arg(x-f.c);
  //cerr << abs(f.c-x) << " " << s << endl;
  return abs(f.c-x)+EPS<f.r and in_angle(s,f.d1,f.d2);
}

inline vector<Fin> enumerateFins(L seg, int l, D d1, D d2){
  vector<Fin> fins;
  fins.pb( Fin(seg.s, l, d1, d2) );
  fins.pb( Fin(seg.s, l, deg_add(d1, PI), deg_add(d2, PI)) );
  fins.pb( Fin(seg.t, l, d1, d2) );
  fins.pb( Fin(seg.t, l, deg_add(d1, PI), deg_add(d2, PI)) );
  return fins;
}

inline vector<Poly> enumerateQuads(L seg, int l, D d1, D d2){
  vector<Poly> quads;
  P base(l,0);

  if( para( seg, L(rotate(base,d1),P(0,0)) ) ){
    P ns = seg.s + unit(seg.s-seg.t)*l, nt = seg.t + unit(seg.t-seg.s)*l;
    P n = unit(normal(seg.t-seg.s).first)*Eps;
    quads.pb( { ns+n, ns-n, nt-n, nt+n });
  }else{
    quads.pb( { rotate(base, d1) + seg.s, rotate(base, deg_add(d1,PI)) + seg.s, rotate(base, deg_add(d1,PI)) + seg.t, rotate(base, d1) + seg.t } );
    if(area(quads.back()) < 0) reverse( all(quads.back()) );
  }
  if( para( seg, L(rotate(base,d2),P(0,0)) ) ){
    P ns = seg.s + unit(seg.s-seg.t)*l, nt = seg.t + unit(seg.t-seg.s)*l;
    P n = unit(normal(seg.t-seg.s).first)*Eps;
    quads.pb( { ns+n, ns-n, nt-n, nt+n });
  }else{
    quads.pb( { rotate(base, d2) + seg.s, rotate(base, deg_add(d2,PI)) + seg.s, rotate(base, deg_add(d2,PI)) + seg.t, rotate(base, d2) + seg.t } );
    if(area(quads.back()) < 0) reverse( all(quads.back()) );
  }

  P n1, n2; tie(n1,n2) = normal(seg.t - seg.s);
  D s = arg(n1);
  if( in_angle(s,d1,d2) ){
    quads.pb( { unit(n1)*l + seg.s, unit(n2)*l + seg.s, unit(n2)*l + seg.t, unit(n1)*l + seg.t } );
    if(area(quads.back()) < 0) reverse( all(quads.back()) );
  }

  return quads;
}

inline bool inValidRegions(P p, const vector< vector<Fin> > &fins, const vector< vector<Poly> > &quads){
  //cout << "(" << p.x << ", " << p.y << ")" << endl;
  int n = fins.size();
  //cerr << n << endl;
  rep(i,n){ for(Fin f : fins[i]){
      //cout << "(" << f.c.x << ", " << f.c.y << ") " << f.r << " " << "[" << f.d1 << ", " << f.d2 << "]" << endl;
      if(in_fin(f, p)){
	//cout << "(" << f.c.x << ", " << f.c.y << ") " << f.r << " " << "[" << f.d1 << ", " << f.d2 << "]" << endl;
	return false;
      }
    }
    //cout << endl;
  }
  rep(i,n) for(Poly q : quads[i]){
    if(in_poly(q, p)){
      //print(q);
      return false;
    }
  }
  return true;
}

inline vector<P> enumeratePassPoints(const vector<L> &segs, int l, int r, int k){
  D d = k * PI/r;
  vector<P> candidates;
  vector<Poly> ext_objs;
  P base(l,0);

  //int id = 0;
  for(L seg : segs){
    Poly p;
    if( para(seg, L(rotate(base, d), P(0,0))) ){
      P z = unit(seg.s-seg.t)*Eps;
      p.pb( rotate(base, d) + seg.s + rotate(z,PI/2) );
      p.pb( rotate(base, deg_add(d,PI)) + seg.s + rotate(z,-PI/2) );
      z *= -1;
      p.pb( rotate(base, d) + seg.t + rotate(z,PI/2) );
      p.pb( rotate(base, deg_add(d,PI)) + seg.t + rotate(z,-PI/2) );
    }else{
      p.pb( rotate(base, d) + seg.s);
      p.pb( rotate(base, deg_add(d,PI)) + seg.s );
      p.pb( rotate(base, deg_add(d,PI)) + seg.t );
      p.pb( rotate(base, d) + seg.t );

      P mid = (seg.s + seg.t)/2;
      rep(i,4) p[i] += unit(p[i]-mid)*Eps;
    }

    if(area(p) < 0) reverse( all(p) );
    ext_objs.pb(p);
    rep(i,4) candidates.pb(p[i]);

    /*
    cerr << id++ << ": ["; 
    rep(i,4) cerr << "(" << p[i].x << ", " << p[i].y << ") ";
    cerr << "]" << endl;
    */
  }

  rep(i, ext_objs.size()) rep(j, i){
    Poly p1 = ext_objs[i], p2 = ext_objs[j];
    rep(ii,p1.size()) rep(jj,p2.size()) {
      L a(p1[ii], p1[(ii+1)%p1.size()]), b(p2[jj], p2[(jj+1)%p2.size()]);
      if(not para(a,b) and is_cp(a,b)) candidates.pb( line_cp(a,b) );
    }
  }

  sort(all(candidates));
  candidates.erase(unique(all(candidates)), candidates.end());
 
  vector<P> res;
  for(P p : candidates){
    bool f = true;
    for(Poly poly : ext_objs){
      if( in_poly(poly, p) ){
	f = false; break;
      }
    }
    if(f) res.pb(p);
  }

  return res;
}

inline vector<P> enumerateSpinPoints(const vector<L> &segs, int l, int r, int k){
  //cerr << "----" << k << "----" << endl;
  int n = segs.size();
  D d1 = k * PI/r, d2 = (k+1) * PI/r;
  vector< vector<Fin> >  fins(n);
  vector< vector<Poly> > quads(n);

  rep(i,n){
    fins[i] = enumerateFins(segs[i], l, d1, d2);
    quads[i] = enumerateQuads(segs[i], l, d1, d2);
  }

  vector<P> candidates;
  rep(i,n){
    candidates.pb(segs[i].s);
    candidates.pb(segs[i].t);
  }

  rep(i,n) rep(j,n){
    //cerr << i << " " << j << endl;
    if(i<j){
      for(Fin f1 : fins[i]){
	for(Fin f2 : fins[j]){
	  vector<P> cps = cir_cir_cp(C(f1.c, f1.r+Eps), C(f2.c, f2.r+Eps));
	  for(P p : cps) candidates.pb(p);
	}
      }
      for(Poly p1 : quads[i]){
	for(Poly p2 : quads[j]){
	  /*
	  cerr << ": ["; 
	  rep(z,4) cerr << "(" << p1[z].x << ", " << p1[z].y << ") ";
	  cerr << "]" << endl;
	  cerr << ": ["; 
	  rep(z,4) cerr << "(" << p2[z].x << ", " << p2[z].y << ") ";
	  cerr << "]" << endl << endl;
	  */
	  rep(i1,p1.size()) rep(i2,p2.size()) {
	    L a(p1[i1], p1[(i1+1)%p1.size()]), b(p2[i2], p2[(i2+1)%p2.size()]);
	    P na = unit(normal(a.t-a.s).second)*Eps, nb = unit(normal(b.t-b.s).second)*Eps;
	    a.s += na; a.t += na; b.s += nb; b.t += nb;
	    if(not para(a,b) and is_cp(a,b)){
	      candidates.pb( line_cp(a,b) );
	      //cerr << "(" << line_cp(a,b).x << ", " << line_cp(a,b).y << ")" << endl;
	    }
	  }
	}
      }
    }
    for(Fin f1 : fins[i]){
      for(Poly p2 : quads[j]){
	rep(i2,p2.size()) {
	  L b(p2[i2], p2[(i2+1)%p2.size()]);
	  P nb = unit(normal(b.t-b.s).first)*Eps;
	  b.s += nb; b.t += nb;
	  vector<P> cps = cir_line_cp(C(f1.c, f1.r+Eps), b);
	  for(P p : cps) candidates.pb(p);
	}
      }
    }
  }

  sort(all(candidates));
  candidates.erase(unique(all(candidates)), candidates.end());

  vector<P> res;
  for(P p : candidates){
    bool tmp = inValidRegions(p, fins, quads);
    //cerr << "(" << p.x << ", " << p.y << "): " << tmp << endl;
    if( tmp ) res.pb(p);
    //cerr << endl;
  }

  return res;
}

inline bool isVisible(P s, P t, const vector<Poly> &ext_objs){    
  L l1(s,t);
  //cerr << s.x << " " << s.y << " " << t.x << " " << t.y << endl;
  for(const Poly& p : ext_objs){
    //print(p);
    //if( in_poly(p,s) or in_poly(p,t) or in_poly(p,(s+t)/2) ) return false;
    rep(i, p.size()){
      L l2(p[i], p[(i+1)%p.size()]);
      //cerr << "  " << p[i].x << " " << p[i].y << " " << p[(i+1)%p.size()].x << " " << p[(i+1)%p.size()].y << endl;
      //if( ccw(l2.s, l2.t, s) == 0 ) return false;
      //cerr << "  s ok" << endl;;
      //if( ccw(l2.s, l2.t, t) == 0 ) return false;
      //cerr << "  t ok" << endl;;
      if(not para(l1,l2) and is_cp(l1, l2)) return false;
      //cerr << "  no cross" << endl;;
    }
  }
  return true;
}

vector<P> points;

inline graph makeGraph(P S, P G, const vector<L> &objs, const vector< vector<P> > &pass_points, const vector< vector<P> > &spin_points, int l){
  int r = pass_points.size();
  vector<int> id_pass(r+1,0), id_spin(r+1,0);
  rep(k,r){
    id_pass[k+1] = id_pass[k] + pass_points[k].size();
    id_spin[k+1] = id_spin[k] + spin_points[k].size();
  }
  //cerr << id_pass[r] << " " << id_spin[r] << endl;
  //for debug
  rep(k,r) rep(i,pass_points[k].size())  points.pb(pass_points[k][i]);
  rep(k,r) rep(i,spin_points[k].size())  points.pb(spin_points[k][i]);
  points.pb(S); points.pb(G);
  
  int N = id_pass[r] + id_spin[r] + 2;
  graph g(N);
  //clock_t pp=0, ps=0, start, end;

  rep(k,r){
    vector<Poly> ext_objs;
    P base(l,0);
    D d = k * PI/r;
    for(L seg : objs){
      ext_objs.pb( { rotate(base, d) + seg.s, rotate(base, deg_add(d,PI)) + seg.s, rotate(base, deg_add(d,PI)) + seg.t, rotate(base, d) + seg.t } );
      if(area(ext_objs.back()) < 0) reverse( all(ext_objs.back()) );
    }
    
    if(k==0){
      int vid = N-2;
      rep(i, pass_points[k].size()){
	int uid = id_pass[k] + i;
	if( isVisible(S, pass_points[k][i], ext_objs) ) g[vid].pb( pii(uid,0) );
      }
      rep(i, spin_points[k].size()){
	int uid = id_pass[r] + id_spin[k] + i;
	if( isVisible(S, spin_points[k][i], ext_objs) ) g[vid].pb( pii(uid,1) );
      }
      int uid = N-1;
      if( isVisible(S, G, ext_objs) ) g[vid].pb( pii(uid,0) );
    }

    //start = clock();
    rep(i, pass_points[k].size()){
      int vid = id_pass[k] + i;
      rep(j, i){
	int uid = id_pass[k] + j;
	if( isVisible(pass_points[k][i], pass_points[k][j], ext_objs) ){
	  g[vid].pb( pii(uid,0) );
	  g[uid].pb( pii(vid,0) );
	}
      }
    }
    //end = clock();
    //pp += end - start;
    
    //start = clock();
    rep(i, pass_points[k].size()){
      int vid = id_pass[k] + i;
      rep(j, spin_points[k].size()){
	int uid = id_pass[r] + id_spin[k] + j;
	if( isVisible(pass_points[k][i], spin_points[k][j], ext_objs) ) g[vid].pb( pii(uid,1) );
      }
    }

    int prv_k = (k+r-1) % r;
    rep(i, pass_points[k].size()){
      int vid = id_pass[k] + i;
      rep(j, spin_points[prv_k].size()){
	int uid = id_pass[r] + id_spin[prv_k] + j;
	if( isVisible(pass_points[k][i], spin_points[prv_k][j], ext_objs) ) g[uid].pb( pii(vid,0) );
      }
    }
    //end = clock();
    //ps += end - start;

    rep(i, pass_points[k].size()){
      int vid = id_pass[k] + i;
      int uid = N-1;
      if( isVisible(pass_points[k][i], G, ext_objs) ){
	  g[vid].pb( pii(uid,0) );
	  g[uid].pb( pii(vid,0) );
      }
    } 
  }
  /*
  cout << "pass-pass: " << (double)pp/CLOCKS_PER_SEC << endl;
  cout << "pass-spin: " << (double)ps/CLOCKS_PER_SEC << endl;
  */
  return g;
}

inline int BFS01(int s, int t, const graph &g){
  int n = g.size();
  vector<int> d(n, -1);
  d[s] = 0;
  deque<int> q; q.push_back(s);

  while(not q.empty()){
    int v = q.front(); q.pop_front();
    //cerr << v << " (" << points[v].x << ", " << points[v].y << ") " <<  d[v] << endl;
    for(pii e : g[v]){
      int u = e.first, c = e.second;
      if(d[u]>=0) continue;
      if(u==t) return d[v] + c;

      d[u] = d[v]+ c;
      if(c == 0) q.push_front(u);
      else q.push_back(u);
    }
  }

  return -1;
}

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int l, r;
  cin >> l >> r;
  P S, G;
  cin >> S.x >> S.y >> G.x >> G.y;
  cerr << fixed << setprecision(10);

  int n;
  cin >> n;
  vector<L> objs(n);
  rep(i,n){
    cin >> objs[i].s.x >> objs[i].s.y >> objs[i].t.x >> objs[i].t.y;
  }

  //clock_t start = clock(), end;

  vector< vector<P> > pass_points(r);
  rep(k,r) pass_points[k] = enumeratePassPoints(objs, l, r, k);
  //end = clock();
  //cout << (double)(end-start)/CLOCKS_PER_SEC << endl;
  
  //start = clock();
  vector< vector<P> > spin_points(r);
  rep(k,r) spin_points[k] = enumerateSpinPoints(objs, l, r, k);
  //end = clock();
  //cout << (double)(end-start)/CLOCKS_PER_SEC << endl;

  //rep(k,r) cerr << k << ": " << pass_points[k].size() << " " << spin_points[k].size() << endl;

  //start = clock();
  graph vis_graph = makeGraph(S, G, objs, pass_points, spin_points, l);
  //end = clock();
  //cout << (double)(end-start)/CLOCKS_PER_SEC << endl;

  /*
  cerr << points.size() << endl;
  int id = 0;
  rep(k,r){
    cerr << "----" << k << "----" << endl;
    for(P p : pass_points[k]) cerr << id++ << ": " << "(" << p.x << ", " << p.y << ")" << endl;
  }
  rep(k,r){
    cerr << "----" << k << "----" << endl;
    for(P p : spin_points[k]) cerr << id++ << ": " << "(" << p.x << ", " << p.y << ")" << endl;
  }
  cerr << endl;
  */

  /*
  rep(i,vis_graph.size()){
    cerr << i << ": ";
    for(auto e : vis_graph[i]) cerr << e.first << ", ";
    cerr << endl;
  }
  */

  int t = vis_graph.size() - 1, s = t-1;
  //start = clock();
  cout << BFS01(s, t, vis_graph) << endl;
  //end = clock();
  //cout << (double)(end-start)/CLOCKS_PER_SEC << endl;
}

Submission Info

Submission Time
Task J - くるくるくるりん
User Darsein
Language C++14 (GCC 5.4.1)
Score 0
Code Size 17158 Byte
Status WA
Exec Time 4543 ms
Memory 2836 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 58
WA × 3
Set Name Test Cases
All 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 00_sample4.txt, big.txt, circle-circle.txt, circle-polygon.txt, guruguru.txt, hard.txt, kill-probably-wa.txt, maximum.txt, minimum.txt, otsu.txt, overlap.txt, parallel.txt, path.txt, random-impossible-1293788.txt, random-impossible-141432.txt, random-impossible-1425649.txt, random-impossible-768269.txt, random-impossible-921909.txt, random-large-1076291.txt, random-large-1493641.txt, random-large-1894450.txt, random-large-1972212.txt, random-large-720209.txt, random-medium-1469155.txt, random-medium-1603266.txt, random-medium-1722587.txt, random-medium-1770943.txt, random-medium-1890000.txt, random-medium-235384.txt, random-medium-240728.txt, random-medium-350641.txt, random-medium-511833.txt, random-medium-877045.txt, random-small-1001193.txt, random-small-1580597.txt, random-small-1600434.txt, random-small-1653849.txt, random-small-16724.txt, random-small-1866077.txt, random-small-1968101.txt, random-small-2017089.txt, random-small-250422.txt, random-small-425800.txt, random-small-480207.txt, random-small-598282.txt, random-small-764379.txt, random-small-77607.txt, random-small-948040.txt, setudou-like.txt, setudou-wa.txt, small-turnable-area.txt, small-turnable-area2.txt, tangent-only.txt, tangent.txt, turn1.txt, turn2.txt, turn3.txt, vertical.txt
Case Name Status Exec Time Memory
00_sample1.txt AC 6 ms 384 KB
00_sample2.txt AC 4 ms 256 KB
00_sample3.txt AC 14 ms 384 KB
00_sample4.txt AC 7 ms 384 KB
big.txt AC 34 ms 512 KB
circle-circle.txt AC 25 ms 512 KB
circle-polygon.txt AC 8 ms 384 KB
guruguru.txt AC 674 ms 848 KB
hard.txt AC 168 ms 812 KB
kill-probably-wa.txt AC 22 ms 384 KB
maximum.txt AC 3375 ms 2832 KB
minimum.txt AC 1 ms 256 KB
otsu.txt AC 534 ms 1304 KB
overlap.txt AC 672 ms 1088 KB
parallel.txt WA 7 ms 384 KB
path.txt AC 2174 ms 2184 KB
random-impossible-1293788.txt AC 1373 ms 1464 KB
random-impossible-141432.txt AC 416 ms 1328 KB
random-impossible-1425649.txt AC 3195 ms 2504 KB
random-impossible-768269.txt AC 1364 ms 1076 KB
random-impossible-921909.txt AC 402 ms 1244 KB
random-large-1076291.txt AC 839 ms 876 KB
random-large-1493641.txt AC 3166 ms 2836 KB
random-large-1894450.txt AC 1317 ms 1216 KB
random-large-1972212.txt AC 1212 ms 1760 KB
random-large-720209.txt AC 1936 ms 2260 KB
random-medium-1469155.txt AC 114 ms 712 KB
random-medium-1603266.txt AC 476 ms 1308 KB
random-medium-1722587.txt AC 785 ms 1584 KB
random-medium-1770943.txt AC 552 ms 984 KB
random-medium-1890000.txt AC 211 ms 824 KB
random-medium-235384.txt AC 433 ms 868 KB
random-medium-240728.txt AC 601 ms 1216 KB
random-medium-350641.txt AC 228 ms 812 KB
random-medium-511833.txt AC 871 ms 1760 KB
random-medium-877045.txt AC 843 ms 2060 KB
random-small-1001193.txt AC 19 ms 512 KB
random-small-1580597.txt AC 98 ms 640 KB
random-small-1600434.txt AC 24 ms 384 KB
random-small-1653849.txt AC 43 ms 512 KB
random-small-16724.txt AC 32 ms 384 KB
random-small-1866077.txt AC 26 ms 548 KB
random-small-1968101.txt AC 109 ms 836 KB
random-small-2017089.txt AC 69 ms 640 KB
random-small-250422.txt AC 116 ms 768 KB
random-small-425800.txt AC 50 ms 512 KB
random-small-480207.txt AC 19 ms 384 KB
random-small-598282.txt AC 114 ms 640 KB
random-small-764379.txt AC 53 ms 572 KB
random-small-77607.txt AC 64 ms 640 KB
random-small-948040.txt AC 101 ms 676 KB
setudou-like.txt WA 23 ms 384 KB
setudou-wa.txt AC 15 ms 384 KB
small-turnable-area.txt AC 17 ms 512 KB
small-turnable-area2.txt AC 178 ms 1052 KB
tangent-only.txt AC 37 ms 512 KB
tangent.txt WA 42 ms 580 KB
turn1.txt AC 95 ms 768 KB
turn2.txt AC 298 ms 1024 KB
turn3.txt AC 29 ms 384 KB
vertical.txt AC 4543 ms 2444 KB