• API
• FAQ
• Tools
• Archive
daily pastebin goal
59%
SHARE
TWEET

# Untitled

a guest Feb 18th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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 long double PI = acos(-1.0);
13.
14. const long double eps = 5e-7;
15.
16. int sgn (long double x) { return x < -eps ? -1 : x > eps; }
17. int cmp(long double a, long double b){ return sgn(a-b);} //cmp(a,b) -1 se a<b
18.
19. struct pt{
20.     long double x, y;
21.     pt(){}
22.     pt (long double a, long double b){
23.         x = a, y = b;
24.     }
25.
26.     long double operator ^(pt p2){
27.         return x*p2.y-y*p2.x;
28.     }
29.     long double operator *(pt p2){
30.         return x*p2.x+y*p2.y;
31.     }
32.
33.     long 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. long double raio[N];
67.
68. vector<pt> pn;
69.
70. const int NN = 1e5+10;
71. vector<pair<int,long double>> g[NN];
72.
73. int vis[NN];
74.
75. long double sq(long double x){
76.     return x*x;
77. }
78.
79. pt forca_mod(pt p, long double m){
80.     long double cm = p.mod();
81.     return pt(p.x*m/cm,p.y*m/cm);
82. }
83.
84. pt rot(pt p, long 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, long double ra, pt b, long double rb){
89.     vector<pt> ans;
90.     if(a==b) return vector<pt>();
91.     if(ra>rb) swap(ra,rb), swap(a, b);
92.     long double dist = (a-b).mod();
93.
94.     if(dist>rb-ra and dist<ra+rb){
95.         long 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.         long 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. long 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.     long 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.     long double rc = raio[ii];
139.     long double dist = dist_p_line(p,pa,pb);
140.     long 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. long double dij(){
173.     set<pair<long double,int>> s;
174.     s.emplace(0,0);
175.
176.     while(!s.empty()){
177.         long 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.             long 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.             long 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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top