Guest User

Untitled

a guest
Feb 18th, 2019
438
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. #define fr(i,n) for(int i = 0;i<n;i++)
  7. #define all(v) (v).begin(),(v).end()
  8. #define eb emplace_back
  9. #define fi first
  10. #define se second
  11.  
  12. const double PI = acos(-1.0);
  13.  
  14. const double eps = 5e-7;
  15.  
  16. int sgn (double x) { return x < -eps ? -1 : x > eps; }
  17. int cmp(double a, double b){ return sgn(a-b);} //cmp(a,b) -1 se a<b
  18.  
  19. struct pt{
  20.     double x, y;
  21.     pt(){}
  22.     pt (double a, double b){
  23.         x = a, y = b;
  24.     }
  25.    
  26.     double operator ^(pt p2){
  27.         return x*p2.y-y*p2.x;
  28.     }
  29.     double operator *(pt p2){
  30.         return x*p2.x+y*p2.y;
  31.     }
  32.    
  33.     double mod(){
  34.         return hypot(x,y);
  35.     }
  36.    
  37.     pt operator -(pt p2){
  38.         return pt(x-p2.x,y-p2.y);
  39.     }
  40.    
  41.     pt operator +(pt p2){
  42.         return pt(x+p2.x,y+p2.y);
  43.     }
  44. };
  45.  
  46. bool operator <(const pt &a, const pt &b){
  47.     if(cmp(a.x,b.x)!=0) return cmp(a.x,b.x)==-1;
  48.     return cmp(a.y,b.y)==-1;
  49. }
  50.  
  51. bool operator <=(const pt &a, const pt &b){
  52.     if(cmp(a.x,b.x)!=0) return cmp(a.x,b.x)==-1;
  53.     return cmp(a.y,b.y)<=0;
  54. }
  55.  
  56. bool operator ==(const pt &a, const pt &b){
  57.     return sgn(a.x-b.x)==0 and sgn(a.y-b.y)==0;
  58. }
  59.  
  60. pt po, pd;
  61.  
  62. int n;
  63.  
  64. const int N = 40;
  65. pt centro[N];
  66. double raio[N];
  67.  
  68. vector<pt> pn;
  69.  
  70. const int NN = 1e5+10;
  71. vector<pair<int,double>> g[NN];
  72.  
  73. int vis[NN];
  74.  
  75. double sq(double x){
  76.     return x*x;
  77. }
  78.  
  79. pt forca_mod(pt p, double m){
  80.     double cm = p.mod();
  81.     return pt(p.x*m/cm,p.y*m/cm);
  82. }
  83.  
  84. pt rot(pt p, double teta){
  85.     return pt(p.x*cos(teta)-p.y*sin(teta),p.y*cos(teta)+p.x*sin(teta));
  86. }
  87.  
  88. vector<pt> intersec_circ_circ(pt a, double ra, pt b, double rb){
  89.     vector<pt> ans;
  90.     if(a==b) return vector<pt>();
  91.     if(ra>rb) swap(ra,rb), swap(a, b);
  92.     double dist = (a-b).mod();
  93.    
  94.     if(dist>rb-ra and dist<ra+rb){
  95.         double dx = fabs(sq(dist)+sq(ra)-sq(rb))/2/dist;
  96.         pt va;
  97.         if(sq(dist)+sq(ra)>sq(rb)) va = forca_mod(b-a,ra);
  98.         else va = forca_mod(a-b,ra);
  99.         double teta = acos(dx/ra);
  100.         ans.eb(a+rot(va,teta));
  101.         ans.eb(a+rot(va,2*PI-teta));
  102.     } else if(dist==ra+rb or dist==rb-ra){
  103.         ans.eb(b+forca_mod(a-b,rb));
  104.     }
  105.    
  106.     sort(all(ans));
  107.     return ans;
  108. }
  109.  
  110. pt pmax(pt pa, pt pb){
  111.     if(pa<pb) return pb;
  112.     return pa;
  113. }
  114.  
  115. double dist_p_line(pt p, pt p1, pt p2){
  116.     pt vb = p2-p1;
  117.     pt vp = p-p1;
  118.     return fabs(vb^vp)/vb.mod();
  119. }
  120.  
  121. bool a_esquerda(pt p, pt pa, pt pb){
  122.     pt vb = pb-pa;
  123.     pt vp = p-pa;
  124.     return (vb^vp)>=0;
  125. }
  126.  
  127. pt proj(pt p, pt pa, pt pb){
  128.     double dist = dist_p_line(p,pa,pb);
  129.     pt vp = forca_mod(pb-pa,dist);
  130.     swap(vp.x,vp.y);
  131.     if(a_esquerda(p,pa,pb)) vp.y*=-1;
  132.     else vp.x*=-1;
  133.     return p+vp;
  134. }
  135.  
  136. pair<pt,pt> intersec_circ_line(int ii, pt pa, pt pb){
  137.     pt p = centro[ii];
  138.     double rc = raio[ii];
  139.     double dist = dist_p_line(p,pa,pb);
  140.     double x = sqrt(sq(rc)-sq(dist));
  141.    
  142.     pair<pt,pt> ans;
  143.     ans.fi = proj(p, pa, pb) + forca_mod(pa-pb,x);
  144.     ans.se = proj(p, pa, pb) - forca_mod(pa-pb,x);
  145.     if(ans.se<ans.fi) swap(ans.fi,ans.se);
  146.     return ans;
  147. }
  148.  
  149. clock_t t_tot;
  150. int cnt;
  151. bool existe(int ii, int jj){
  152.     pt pa = pn[ii];
  153.     pt pb = pn[jj];
  154.     if(pb<pa) swap(pa,pb);
  155.    
  156.     vector<pair<pt,pt>> v;
  157.    
  158.     fr(i,n){
  159.         if(dist_p_line(centro[i],pa,pb)<raio[i]) v.eb(intersec_circ_line(i,pa,pb));
  160.     }
  161.    
  162.     sort(all(v));
  163.    
  164.     pt pc = pa;
  165.     for(auto &par : v){
  166.         if(par.fi<=pc) pc = pmax(pc,par.se);
  167.     }
  168.    
  169.     return pb<=pc;
  170. }
  171.  
  172. double dij(){
  173.     set<pair<double,int>> s;
  174.     s.emplace(0,0);
  175.    
  176.     while(!s.empty()){
  177.         double curd;
  178.         int no;
  179.         tie(curd,no) = *s.begin();
  180.         s.erase(s.begin());
  181.        
  182.         if(vis[no]) continue;
  183.         vis[no] = 1;
  184.        
  185.         if(no==1) return curd;
  186.        
  187.         for(auto &par : g[no]){
  188.             int it;
  189.             double c;
  190.             tie(it,c) = par;
  191.             if(!vis[it]){
  192.                 s.emplace(curd+c,it);
  193.             }
  194.         }
  195.     }
  196.    
  197.     puts("impossible");
  198.     exit(0);
  199. }
  200.  
  201. int main(){
  202.     scanf("%lf%lf", &po.x, &po.y);
  203.     scanf("%lf%lf", &pd.x, &pd.y);
  204.     cin >> n;
  205.    
  206.     fr(i,n){
  207.         scanf("%lf%lf%lf", &centro[i].x, &centro[i].y, raio+i);
  208.     }
  209.    
  210.     pn.eb(po);
  211.     pn.eb(pd);
  212.    
  213.     fr(i,n){
  214.         fr(j,i){
  215.             vector<pt> cur = intersec_circ_circ(centro[i],raio[i],centro[j],raio[j]);
  216.             for(auto &p : cur) pn.eb(p);
  217.         }
  218.     }
  219.    
  220.     fr(i,pn.size()) fr(j,i){
  221.         if(existe(i,j)){
  222.             double c = (pn[i]-pn[j]).mod();
  223.             g[i].eb(j,c);
  224.             g[j].eb(i,c);
  225.         }
  226.     }
  227.     printf("%.15lf\n", dij());
  228. }
Add Comment
Please, Sign In to add comment