fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Vert{double x,y,z;};
  5. struct Edge{int u,v;};
  6. struct Tri{int v[3]; int e[3]; int opp[3];};
  7. struct ActEdge{int e1,e2; double a,b;};
  8.  
  9. struct DSURollback{
  10.     vector<int> parent, sz;
  11.     vector<double> A,B;
  12.     struct Hist{int rv; int sz_ru; double A_ru; double B_ru;};
  13.     vector<Hist> st;
  14.     void init(int n){
  15.         parent.resize(n);
  16.         sz.resize(n);
  17.         A.assign(n,0.0);
  18.         B.assign(n,0.0);
  19.         st.clear();
  20.         for(int i=0;i<n;i++){
  21.             parent[i]=i;
  22.             sz[i]=1;
  23.         }
  24.     }
  25.     int find(int x){
  26.         while(parent[x]!=x) x=parent[x];
  27.         return x;
  28.     }
  29.     bool unite(int u,int v,double a,double b){
  30.         int ru=find(u), rv=find(v);
  31.         if(ru==rv) return false;
  32.         if(sz[ru]<sz[rv]) swap(ru,rv);
  33.         st.push_back({rv,sz[ru],A[ru],B[ru]});
  34.         parent[rv]=ru;
  35.         sz[ru]+=sz[rv];
  36.         A[ru] += A[rv] + a;
  37.         B[ru] += B[rv] + b;
  38.         return true;
  39.     }
  40.     void rollback(int target){
  41.         while((int)st.size()>target){
  42.             auto h=st.back(); st.pop_back();
  43.             int rv=h.rv;
  44.             int ru=parent[rv];
  45.             parent[rv]=rv;
  46.             sz[ru]=h.sz_ru;
  47.             A[ru]=h.A_ru;
  48.             B[ru]=h.B_ru;
  49.         }
  50.     }
  51. };
  52.  
  53. int main(){
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(nullptr);
  56.  
  57.     int t;
  58.     if(!(cin>>t)) return 0;
  59.     cout.setf(std::ios::fixed);
  60.     cout<<setprecision(999);
  61.     while(t--){
  62.         int w,l; int n,m;
  63.         cin>>w>>l>>n>>m;
  64.         vector<Vert> vert(n+1);
  65.         int swId=-1,seId=-1,nwId=-1,neId=-1;
  66.         for(int i=1;i<=n;i++){
  67.             int xi,yi,zi;
  68.             cin>>xi>>yi>>zi;
  69.             vert[i]={double(xi),double(yi),double(zi)};
  70.             if(xi==0 && yi==0) swId=i;
  71.             if(xi==w && yi==0) seId=i;
  72.             if(xi==0 && yi==l) nwId=i;
  73.             if(xi==w && yi==l) neId=i;
  74.         }
  75.         double minWest=min(vert[swId].z, vert[nwId].z);
  76.         double maxWest=max(vert[swId].z, vert[nwId].z);
  77.         double minEast=min(vert[seId].z, vert[neId].z);
  78.         double maxEast=max(vert[seId].z, vert[neId].z);
  79.         double overlapLow=max(minWest, minEast);
  80.         double overlapHigh=min(maxWest, maxEast);
  81.  
  82.         unordered_map<long long,int> edgeMap;
  83.         edgeMap.reserve(m*6);
  84.         vector<Edge> edges;
  85.         edges.reserve(m*3);
  86.         vector<Tri> triangles;
  87.         triangles.reserve(m);
  88.         vector<vector<int>> incidentTris(n+1);
  89.  
  90.         auto getEdgeId = [&](int a,int b)->int{
  91.             if(a>b) swap(a,b);
  92.             long long key = (long long)a*60000LL + (long long)b;
  93.             auto it=edgeMap.find(key);
  94.             if(it!=edgeMap.end()) return it->second;
  95.             int id=(int)edges.size();
  96.             edges.push_back({a,b});
  97.             edgeMap[key]=id;
  98.             return id;
  99.         };
  100.  
  101.         for(int ti=0;ti<m;ti++){
  102.             int a,b,c1;
  103.             cin>>a>>b>>c1;
  104.             int e_ab=getEdgeId(a,b);
  105.             int e_bc=getEdgeId(b,c1);
  106.             int e_ca=getEdgeId(c1,a);
  107.             Tri tr;
  108.             tr.v[0]=a; tr.v[1]=b; tr.v[2]=c1;
  109.             tr.e[0]=e_ab; tr.e[1]=e_bc; tr.e[2]=e_ca;
  110.             tr.opp[0]=e_bc; tr.opp[1]=e_ca; tr.opp[2]=e_ab;
  111.             int idx=(int)triangles.size();
  112.             triangles.push_back(tr);
  113.             incidentTris[a].push_back(idx);
  114.             incidentTris[b].push_back(idx);
  115.             incidentTris[c1].push_back(idx);
  116.         }
  117.  
  118.         int E=(int)edges.size();
  119.         int startEdgeId = getEdgeId(swId,nwId);
  120.         int endEdgeId = getEdgeId(seId,neId);
  121.  
  122.         vector<int> order(n);
  123.         iota(order.begin(), order.end(), 1);
  124.         sort(order.begin(), order.end(), [&](int u,int v){ return vert[u].z < vert[v].z; });
  125.         vector<int> pos(n+1);
  126.         for(int i=0;i<n;i++) pos[order[i]]=i;
  127.  
  128.         int N=n;
  129.         int sizeTree=1; while(sizeTree<N) sizeTree<<=1;
  130.         vector<vector<ActEdge>> seg(2*sizeTree);
  131.  
  132.         auto addRange=[&](int L,int R,const ActEdge &ae){
  133.             int l=L+sizeTree, r=R+sizeTree;
  134.             while(l<r){
  135.                 if(l&1) seg[l++].push_back(ae);
  136.                 if(r&1) seg[--r].push_back(ae);
  137.                 l>>=1; r>>=1;
  138.             }
  139.         };
  140.  
  141.         for(const auto &tr: triangles){
  142.             int ids[3]={tr.v[0],tr.v[1],tr.v[2]};
  143.             int ordIdx[3]={0,1,2};
  144.             sort(ordIdx, ordIdx+3, [&](int ii,int jj){ return vert[ ids[ii] ].z < vert[ ids[jj] ].z; });
  145.             int lo=ids[ordIdx[0]];
  146.             int mi=ids[ordIdx[1]];
  147.             int hi=ids[ordIdx[2]];
  148.             int plo=pos[lo], pmi=pos[mi], phi=pos[hi];
  149.  
  150.             int L=plo+1, R=pmi;
  151.             if(L<R){
  152.                 int sing=lo; int q=mi; int r=hi;
  153.                 const Vert &S=vert[sing], &Q=vert[q], &RR=vert[r];
  154.                 double dx1=Q.x-S.x, dy1=Q.y-S.y;
  155.                 double dx2=RR.x-S.x, dy2=RR.y-S.y;
  156.                 double denom1=Q.z-S.z, denom2=RR.z-S.z;
  157.                 double kx=dx1/denom1 - dx2/denom2;
  158.                 double ky=dy1/denom1 - dy2/denom2;
  159.                 double normK=sqrt(kx*kx+ky*ky);
  160.                 double aCoeff=+normK;
  161.                 double bCoeff=-S.z*normK;
  162.                 int e1=-1,e2=-1;
  163.                 for(int j=0;j<3;j++){
  164.                     int eid=tr.e[j];
  165.                     auto &ed=edges[eid];
  166.                     if(ed.u==sing||ed.v==sing){
  167.                         if(e1==-1) e1=eid; else e2=eid;
  168.                     }
  169.                 }
  170.                 ActEdge ae{e1,e2,aCoeff,bCoeff};
  171.                 addRange(L,R,ae);
  172.             }
  173.  
  174.             L=pmi+1; R=phi;
  175.             if(L<R){
  176.                 int sing=hi; int q=lo; int r=mi;
  177.                 const Vert &S=vert[sing], &Q=vert[q], &RR=vert[r];
  178.                 double dx1=Q.x-S.x, dy1=Q.y-S.y;
  179.                 double dx2=RR.x-S.x, dy2=RR.y-S.y;
  180.                 double denom1=Q.z-S.z, denom2=RR.z-S.z;
  181.                 double kx=dx1/denom1 - dx2/denom2;
  182.                 double ky=dy1/denom1 - dy2/denom2;
  183.                 double normK=sqrt(kx*kx+ky*ky);
  184.                 double aCoeff=-normK;
  185.                 double bCoeff=+S.z*normK;
  186.                 int e1=-1,e2=-1;
  187.                 for(int j=0;j<3;j++){
  188.                     int eid=tr.e[j];
  189.                     auto &ed=edges[eid];
  190.                     if(ed.u==sing||ed.v==sing){
  191.                         if(e1==-1) e1=eid; else e2=eid;
  192.                     }
  193.                 }
  194.                 ActEdge ae{e1,e2,aCoeff,bCoeff};
  195.                 addRange(L,R,ae);
  196.             }
  197.         }
  198.  
  199.         DSURollback dsu;
  200.         dsu.init(E);
  201.         double ans=numeric_limits<double>::infinity();
  202.  
  203.         function<void(int,int,int)> dfs = [&](int idx,int l,int r){
  204.             int before=(int)dsu.st.size();
  205.             for(auto &ae: seg[idx]){
  206.                 dsu.unite(ae.e1, ae.e2, ae.a, ae.b);
  207.             }
  208.  
  209.             if(r-l==1){
  210.                 int leaf=l;
  211.                 if(leaf < N){
  212.                     int vid=order[leaf];
  213.                     double c = vert[vid].z;
  214.                     if(!(c < overlapLow || c > overlapHigh)){
  215.                         int rootStart=dsu.find(startEdgeId);
  216.                         int rootEnd=dsu.find(endEdgeId);
  217.                         double lenStart=dsu.A[rootStart]*c + dsu.B[rootStart];
  218.                         double lenEnd=dsu.A[rootEnd]*c + dsu.B[rootEnd];
  219.  
  220.                         double best=numeric_limits<double>::infinity();
  221.  
  222.                         if(rootStart==rootEnd){
  223.                             best=lenStart;
  224.                         }
  225.  
  226.                         double minStartCost=numeric_limits<double>::infinity();
  227.                         double minEndCost=numeric_limits<double>::infinity();
  228.                         if(vid==swId || vid==nwId) minStartCost=0.0;
  229.                         if(vid==seId || vid==neId) minEndCost=0.0;
  230.  
  231.                         for(int tIdx: incidentTris[vid]){
  232.                             const Tri &tr=triangles[tIdx];
  233.                             int idxv;
  234.                             if(tr.v[0]==vid) idxv=0;
  235.                             else if(tr.v[1]==vid) idxv=1;
  236.                             else idxv=2;
  237.                             int a=tr.v[(idxv+1)%3];
  238.                             int b=tr.v[(idxv+2)%3];
  239.                             double za=vert[a].z, zb=vert[b].z;
  240.                             double da=za - c, db=zb - c;
  241.                             if(!((da>0 && db<0) || (da<0 && db>0))) continue;
  242.                             int eOpp=tr.opp[idxv];
  243.                             int rootOpp=dsu.find(eOpp);
  244.                             double lenOppRoot=dsu.A[rootOpp]*c + dsu.B[rootOpp];
  245.                             const Vert &Av=vert[a]; const Vert &Bv=vert[b]; const Vert &Vv=vert[vid];
  246.                             double tpar=(c - Av.z) / (Bv.z - Av.z);
  247.                             double px=Av.x + tpar*(Bv.x - Av.x);
  248.                             double py=Av.y + tpar*(Bv.y - Av.y);
  249.                             double segLen=hypot(px - Vv.x, py - Vv.y);
  250.  
  251.                             if(rootOpp==rootStart){
  252.                                 double cost = ((eOpp==startEdgeId)?0.0:lenStart) + segLen;
  253.                                 if(cost<minStartCost) minStartCost=cost;
  254.                             }
  255.                             if(rootOpp==rootEnd){
  256.                                 double cost = ((eOpp==endEdgeId)?0.0:lenEnd) + segLen;
  257.                                 if(cost<minEndCost) minEndCost=cost;
  258.                             }
  259.                         }
  260.  
  261.                         if(minStartCost<numeric_limits<double>::infinity() && minEndCost<numeric_limits<double>::infinity()){
  262.                             double tot=minStartCost+minEndCost;
  263.                             if(tot<best) best=tot;
  264.                         }
  265.  
  266.                         if(best<ans) ans=best;
  267.                     }
  268.                 }
  269.             }else{
  270.                 int mid=(l+r)/2;
  271.                 dfs(idx*2,l,mid);
  272.                 dfs(idx*2+1,mid,r);
  273.             }
  274.  
  275.             dsu.rollback(before);
  276.         };
  277.  
  278.         dfs(1,0,sizeTree);
  279.  
  280.         if(std::isinf(ans)){
  281.             cout<<"impossible\n";
  282.         }else{
  283.             cout<<ans<<"\n";
  284.         }
  285.     }
  286.  
  287.     return 0;
  288. }
  289.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/49eMgb
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!