#include #include #include #include #include #include using namespace std; #if defined VIZ #define CONSTRUCT #include #include #endif typedef vector VI; typedef unordered_set HI; const double EPS=1e-9; const double INF=numeric_limits::infinity(); template T sq(T x) { return x*x; } // time <= 8\sqrt(4000) + \sum(red)/2 < 910 const int TMAX = 910; int n; vector Ti,g0,gi; vector green; vector red; double normalize(int i, double t) { // return t \in [0, T_i) t+=EPS; t-=g0[i]; t=fmod(t,Ti[i]); t+=Ti[i]; t=fmod(t,Ti[i]); t-=EPS; return t; } bool isitgreen(int i, double t) { return normalize(i,t)-EPStgreen) { feasible = false; return; } fromtstart(igreen, tgreen); #if defined DEBUG if (feasible) { cerr << "Considering extra from " << start.xstart << " at " << start.tstart << " green " << igreen << " at " << tgreen << endl; info(); } #endif } bool canitgothere(double x) const { return xstart < x + EPS and x - EPS < iend*1000; } double t(double x) const { double dx=x-xstart; double dt=sqrt(2*dx); return tstart+dt; } bool canstartfrom(const parabola& p) { if (not p.canitgothere(xstart)) return false; double tp; if (xstart+EPS > p.iend*1000) tp = p.tend; else tp = p.t(xstart); return tp-EPS parabolas; int numoriginal; vector> extrapointers; double best; #if defined CONSTRUCT VI parent; int besti; #endif void bfs() { best=INF; HI unseen; unseen.reserve(numoriginal); for (int i=1;i q; q.push(0); while(not q.empty()) { int v = q.front(); q.pop(); const parabola& p = parabolas[v]; #if defined DEBUG cerr << "Visiting " << p.xstart << ' ' << p.tstart << " -> " << p.iend*1000 << ' ' << p.t(p.iend*1000) << endl; #endif if (p.iend==n) { #if defined CONSTRUCT if (p.tend> n; green.resize(n); red.resize(n); Ti.resize(n); g0.resize(n); gi.resize(n); green[0].push_back(0); for (int i=1;i> firstgreen >> Tgreen >> Tred; T=Tgreen+Tred; g0[i]=firstgreen; gi[i]=Tgreen; Ti[i]=T; firstred=firstgreen+Tgreen; firstred%=T; for (int t=firstgreen;t<=TMAX;t+=T) green[i].push_back(t); for (int t=firstred;t<=TMAX;t+=T) red[i].push_back(t); } for (int igreen=0;igreen=tgreen) break; parabola p(igreen,tgreen,ired,tred); if (p.feasible) parabolas.push_back(p); } } } } numoriginal = parabolas.size(); for (int igreen=0;igreen extraparabolas; for (int tgreen : green[igreen]) { for (int i=0;i events; for (auto y : green[i]) events[y]=1; for (auto y : red[i]) events[y]=-1; if (events.find(0)==events.end()) events.insert(make_pair(0.,-events.begin()->second)); events[best]=0; for (auto it = events.begin();it->firstsecond!=-1) {++it; continue;} cout << boost::format("draw((%1%,%2%) -- (%1%,%3%),p=red+2);") % (i*1000) % it->first % (it++)->first << endl; } } while(true) { cout << parabolas[besti] << endl; if (parabolas[besti].xstart==0) break; cout << boost::format("draw((%1%,%2%) -- (%1%,%3%),p=blue+dotted);") % parabolas[besti].xstart % parabolas[besti].tstart % parabolas[parent[besti]].t(parabolas[besti].xstart) << endl; besti=parent[besti]; } cout << "currentpicture = scale(0.125,1.5)*currentpicture;" << endl; #else cout.precision(10); cout << best << endl; #endif #if defined CONSTRUCT and not defined VIZ check(); #endif }