#include #include #include #include #include #include #include #include using namespace std; static const double EP = 1e-7, WEP = 1e-3, BUF = 1e-3, TL = 0.70; static int BLIM = 8, NEAR = 10, PERM_LIM = 6; enum { ACT_PU, ACT_DEL, ACT_RET, ACT_WAIT, ACT_WP, ACT_CHG, ACT_CHGDONE }; struct Pt { double x, y, t; int act; int pid = -1; vector grp; }; struct Zone { int typ; double cx, cy, rad, x0, y0, x1, y1, ta, tb; }; struct Eval { bool ok; double eng, fin; }; static double HX, HY; static int NP, NZ; static vector PX, PY, PW, PDL, DCAP, CSX, CSY, BBx0, BBy0, BBx1, BBy1; static vector PID, DID; static vector ZV; static inline bool circHit(double ax, double ay, double bx, double by, double cx, double cy, double r, double &lo, double &hi) { double dx=bx-ax, dy=by-ay, L2=dx*dx+dy*dy, L=sqrt(L2); if (L2<1e-12) { double d2=(ax-cx)*(ax-cx)+(ay-cy)*(ay-cy); if (d2<=r*r){lo=hi=0;return true;} return false; } double a=L2, b=2*(dx*(ax-cx)+dy*(ay-cy)), c=(ax-cx)*(ax-cx)+(ay-cy)*(ay-cy)-r*r; double disc=b*b-4*a*c; if(disc<0) return false; double sq=sqrt(disc), t1=(-b-sq)/(2*a), t2=(-b+sq)/(2*a); lo=max(0.0,t1)*L; hi=min(1.0,t2)*L; return lo<=hi; } static inline bool boxHit(double ax, double ay, double bx, double by, double x0, double y0, double x1, double y1, double &lo, double &hi) { double dx=bx-ax, dy=by-ay, L=sqrt(dx*dx+dy*dy); if (L<1e-9) { if(ax>=x0&&ax<=x1&&ay>=y0&&ay<=y1){lo=hi=0;return true;} return false; } double t0=0, t1=1; if(fabs(dx)<1e-12){if(axx1)return false;} else{double a=(x0-ax)/dx,b=(x1-ax)/dx;if(a>b)swap(a,b);t0=max(t0,a);t1=min(t1,b);} if(fabs(dy)<1e-12){if(ayy1)return false;} else{double a=(y0-ay)/dy,b=(y1-ay)/dy;if(a>b)swap(a,b);t0=max(t0,a);t1=min(t1,b);} if(t0>t1)return false; lo=t0*L; hi=t1*L; return true; } static inline bool zoneHit(double ax, double ay, double bx, double by, int idx, double &lo, double &hi) { const Zone &z=ZV[idx]; if(z.typ==0) return circHit(ax,ay,bx,by,z.cx,z.cy,z.rad+BUF,lo,hi); return boxHit(ax,ay,bx,by,z.x0-BUF,z.y0-BUF,z.x1+BUF,z.y1+BUF,lo,hi); } // returns earliest departure time from A to B starting no earlier than t0 static double earliestDepart(double ax, double ay, double bx, double by, double t0) { if(NZ==0) return t0; double L=hypot(bx-ax,by-ay); if(L<1e-9) return t0; double sx0=min(ax,bx),sy0=min(ay,by),sx1=max(ax,bx),sy1=max(ay,by); static vector hit; static vector hlo,hhi; hit.clear(); hlo.clear(); hhi.clear(); double lo,hi; for(int i=0;isx1+BUF||BBy1[i]sy1+BUF) continue; if(zoneHit(ax,ay,bx,by,i,lo,hi)){hit.push_back(i);hlo.push_back(lo);hhi.push_back(hi);} } if(hit.empty()) return t0; double td=t0; int lim=(int)hit.size()+2; for(int it=0;ittd)td=ZV[i].tb+WEP;clash=true;} } if(!clash) break; } bool clash=false; for(int j=0;j<(int)hit.size();j++){ int i=hit[j]; double ol=td+hlo[j], oh=td+hhi[j]; if(ol<=ZV[i].tb+EP && ZV[i].ta-EP<=oh){clash=true;break;} } if(clash){double mx=td;for(int j=0;j<(int)hit.size();j++)mx=max(mx,ZV[hit[j]].tb+WEP);td=mx;} return td; } // plans a single leg A->B; may insert a waypoint to avoid NFZ static void planLeg(double ax, double ay, double bx, double by, double t0, double &arrT, double &flown, bool &hasWP, double &wpx, double &wpy) { double L=hypot(bx-ax,by-ay); hasWP=false; wpx=wpy=0; if(L<1e-9){arrT=t0;flown=0;return;} double td=earliestDepart(ax,ay,bx,by,t0); arrT=td+L; flown=L; if(arrT<=t0+L+1e-9) return; double ux=(bx-ax)/L,uy=(by-ay)/L,nx=-uy,ny=ux; double sx0=min(ax,bx),sy0=min(ay,by),sx1=max(ax,bx),sy1=max(ay,by); for(int i=0;isx1+BUF||BBy1[i]sy1+BUF) continue; double s1,s2; if(!zoneHit(ax,ay,bx,by,i,s1,s2)) continue; const Zone &z=ZV[i]; double cpts[8][2]; int nc=0; if(z.typ==0){ double offs[3]={1.3,2.0,3.0}; for(double m:offs){double o=z.rad*m+1;cpts[nc][0]=z.cx+nx*o;cpts[nc][1]=z.cy+ny*o;nc++;cpts[nc][0]=z.cx-nx*o;cpts[nc][1]=z.cy-ny*o;nc++;} } else { double pad=2; cpts[nc][0]=z.x0-pad;cpts[nc][1]=z.y0-pad;nc++; cpts[nc][0]=z.x1+pad;cpts[nc][1]=z.y0-pad;nc++; cpts[nc][0]=z.x0-pad;cpts[nc][1]=z.y1+pad;nc++; cpts[nc][0]=z.x1+pad;cpts[nc][1]=z.y1+pad;nc++; } for(int c=0;c &out) { double arr,fl; bool hw; double wx,wy; planLeg(ax,ay,bx,by,t0,arr,fl,hw,wx,wy); double L=hypot(bx-ax,by-ay); if(L<1e-9){out.push_back(Pt{bx,by,t0,ACT_WP});return t0;} if(!hw){ double td=earliestDepart(ax,ay,bx,by,t0); if(td>t0+1e-9) out.push_back(Pt{ax,ay,td,ACT_WAIT}); out.push_back(Pt{bx,by,td+L,ACT_WP}); return td+L; } double L1=hypot(wx-ax,wy-ay),td1=earliestDepart(ax,ay,wx,wy,t0),a1=td1+L1; if(td1>t0+1e-9) out.push_back(Pt{ax,ay,td1,ACT_WAIT}); out.push_back(Pt{wx,wy,a1,ACT_WP}); double L2=hypot(bx-wx,by-wy),td2=earliestDepart(wx,wy,bx,by,a1),a2=td2+L2; if(td2>a1+1e-9) out.push_back(Pt{wx,wy,td2,ACT_WAIT}); out.push_back(Pt{bx,by,a2,ACT_WP}); return a2; } static bool segCrossesZone(double ax, double ay, double bx, double by, double t0) { double sx0=min(ax,bx),sy0=min(ay,by),sx1=max(ax,bx),sy1=max(ay,by); for(int i=0;isx1+1e-9||BBy1[i]sy1+1e-9) continue; const Zone &z=ZV[i]; double lo,hi; bool h; if(z.typ==0) h=circHit(ax,ay,bx,by,z.cx,z.cy,z.rad,lo,hi); else h=boxHit(ax,ay,bx,by,z.x0,z.y0,z.x1,z.y1,lo,hi); if(!h) continue; double ol=t0+lo,oh=t0+hi; if(ol<=z.tb&&z.ta<=oh) return true; } return false; } static bool checkTrip(const vector &p, double cap) { int n=(int)p.size(); if(n<2) return false; if(p[0].act!=ACT_PU) return false; if(fabs(p[0].x-HX)>1e-6||fabs(p[0].y-HY)>1e-6) return false; if(p[n-1].act!=ACT_RET) return false; double load=0; for(int id:p[0].grp) load+=PW[id]; if(load>cap+1e-6) return false; double bat=500; static vector seen; seen.clear(); for(int i=1;i1e-6){ if(fabs(dt-d)>1e-3+1e-6*d) return false; double e=d*(1+load); bat-=e; if(bat<-1e-3) return false; if(segCrossesZone(p[i-1].x,p[i-1].y,p[i].x,p[i].y,p[i-1].t)) return false; } else if(p[i].act==ACT_CHGDONE&&p[i-1].act==ACT_CHG){bat+=2*dt;if(bat>500)bat=500;} if(p[i].act==ACT_DEL){ int id=p[i].pid; if(id<0) return false; for(int q:seen) if(q==id) return false; seen.push_back(id); if(fabs(p[i].x-PX[id])>1e-6||fabs(p[i].y-PY[id])>1e-6) return false; if(p[i].t>PDL[id]+1e-6) return false; load-=PW[id]; if(load<-1e-6) return false; } else if(p[i].act==ACT_CHG){ bool found=false; for(int s=0;s<(int)CSX.size();s++) if(fabs(p[i].x-CSX[s])<1e-6&&fabs(p[i].y-CSY[s])<1e-6){found=true;break;} if(!found) return false; } else if(p[i].act==ACT_RET){ if(fabs(p[i].x-HX)>1e-6||fabs(p[i].y-HY)>1e-6) return false; } } return true; } static Eval scoreSeq(double T0, const int *seq, int k) { double load=0; for(int j=0;jPDL[i]+1e-6) return {false,0,0}; totD+=fl; totWD+=PW[i]*totD; t=arr; px=PX[i]; py=PY[i]; } planLeg(px,py,HX,HY,t,arr,fl,hw,wx,wy); double eng=totD+fl+totWD; if(eng>500+1e-6) return {false,0,0}; return {true,eng,arr}; } static Eval pickOrder(double T0, vector batch, vector &out) { int k=(int)batch.size(); Eval best{false,1e18,1e18}; if(k<=PERM_LIM){ sort(batch.begin(),batch.end()); do{ Eval r=scoreSeq(T0,batch.data(),k); if(r.ok&&(r.eng ord=batch; Eval r=scoreSeq(T0,ord.data(),k); if(r.ok){ best=r; out=ord; bool imp=true; int it=0; while(imp&&it++<60){ imp=false; for(int a=0;a &seq, vector &out) { out.push_back(Pt{HX,HY,T0,ACT_PU,-1,seq}); double t=T0,px=HX,py=HY; for(int i:seq){t=addLeg(px,py,PX[i],PY[i],t,out);out.back().act=ACT_DEL;out.back().pid=i;px=PX[i];py=PY[i];} addLeg(px,py,HX,HY,t,out); out.back().act=ACT_RET; } // plans deliver->charge->return for a single package that needs mid-trip recharge static bool buildChargeRoute(double T0, int pi, double cap, vector &out, double &endT) { double w=PW[pi]; double bestEnd=1e18; bool found=false; vector bestPts; for(int s=0;s<(int)CSX.size();s++){ double arr,fl; bool hw; double wx,wy; planLeg(HX,HY,PX[pi],PY[pi],T0,arr,fl,hw,wx,wy); double e1=fl*(1+w); if(e1>500+1e-6||arr>PDL[pi]+1e-6) continue; double batD=500-e1; double arr2,fl2; planLeg(PX[pi],PY[pi],CSX[s],CSY[s],arr,arr2,fl2,hw,wx,wy); if(fl2>batD+1e-6) continue; double batS=batD-fl2; double arr3,fl3; planLeg(CSX[s],CSY[s],HX,HY,arr2,arr3,fl3,hw,wx,wy); if(fl3>500+1e-6) continue; double need=max(0.0,fl3-batS),ct=need/2.0,tcc=arr2+ct; planLeg(CSX[s],CSY[s],HX,HY,tcc,arr3,fl3,hw,wx,wy); if(fl3>batS+need+1e-6){need=max(0.0,fl3-batS);ct=need/2.0;tcc=arr2+ct;} vector pts; pts.push_back(Pt{HX,HY,T0,ACT_PU,-1,vector{pi}}); double t1=addLeg(HX,HY,PX[pi],PY[pi],T0,pts); pts.back().act=ACT_DEL; pts.back().pid=pi; double t2=addLeg(PX[pi],PY[pi],CSX[s],CSY[s],t1,pts); pts.back().act=ACT_CHG; pts.push_back(Pt{CSX[s],CSY[s],t2+ct,ACT_CHGDONE}); double t3=addLeg(CSX[s],CSY[s],HX,HY,t2+ct,pts); pts.back().act=ACT_RET; if(checkTrip(pts,cap)&&t3(cin)),istreambuf_iterator()); Json::Value doc; Json::CharReaderBuilder rb; string errs; istringstream ss(raw); Json::parseFromStream(rb,ss,&doc,&errs); double mw=doc["map_size"][0].asDouble(),mh=doc["map_size"][1].asDouble(); HX=mw/2.0; HY=mh/2.0; Json::Value jdrones=doc["drones"],jpkgs=doc["deliveries"]; Json::Value jzones=doc.get("no_fly_zones",Json::Value(Json::arrayValue)); Json::Value jcs=doc.get("charging_stations",Json::Value(Json::arrayValue)); Json::Value manifest(Json::arrayValue); int nd=(int)jdrones.size(); DID.resize(nd); DCAP.resize(nd); double maxCap=0; for(int i=0;i1500) PERM_LIM=4; vector done(NP,0),needCS(NP,0); for(int i=0;imaxCap+1e-9||dw>PDL[i]+1e-6||e1>500) done[i]=1; else if(rt>500){if(CSX.empty())done[i]=1;else needCS[i]=1;} } vector rem; for(int i=0;i uavT(nd,0.0); vector> uavPts(nd); while(alive>0){ if(chrono::duration(chrono::steady_clock::now()-tstart).count()>TL) break; if((int)rem.size()>2*alive+16){vector nr;nr.reserve(alive);for(int i:rem)if(!done[i])nr.push_back(i);rem.swap(nr);} int ui=-1; double bd=1e18; for(int k=0;k<(int)rem.size();k++){int i=rem[k];if(done[i])continue;if(PDL[i]=PW[u]-1e-9&&(g<0||uavT[j] cn;double ce;if(buildChargeRoute(T0,u,DCAP[g],cn,ce)){for(auto &x:cn)uavPts[g].push_back(x);uavT[g]=ce;}done[u]=1;alive--;continue;} {int one[1]={u};if(!scoreSeq(T0,one,1).ok){done[u]=1;alive--;continue;}} vector batch={u}; double cx=PX[u],cy=PY[u]; while((int)batch.size()cap+1e-9) continue; double ddx=PX[i]-cx,ddy=PY[i]-cy,dd=ddx*ddx+ddy*ddy; if(cnt0&&bdd[p-1]>dd){bdd[p]=bdd[p-1];bpp[p]=bpp[p-1];p--;}bdd[p]=dd;bpp[p]=k;cnt++;} else if(dd0&&bdd[p-1]>dd){bdd[p]=bdd[p-1];bpp[p]=bpp[p-1];p--;}bdd[p]=dd;bpp[p]=k;} } if(!cnt) break; bool added=false; for(int q=0;q tmp=batch; tmp.push_back(i); sort(tmp.begin(),tmp.end(),[](int a,int b){return PDL[a] ord; Eval best=pickOrder(T0,batch,ord); vector tn; if(best.ok){buildRoute(T0,ord,tn);if(checkTrip(tn,DCAP[g])){for(auto &x:tn)uavPts[g].push_back(x);uavT[g]=best.fin;for(int b:batch)if(!done[b]){done[b]=1;alive--;}continue;}} {vector so={u},sord;Eval sb=pickOrder(T0,so,sord);vectorsn;if(sb.ok){buildRoute(T0,sord,sn);if(checkTrip(sn,DCAP[g])){for(auto &x:sn)uavPts[g].push_back(x);uavT[g]=sb.fin;done[u]=1;alive--;continue;}}} done[u]=1;alive--; } for(int g=0;g