Advertisement
Guest User

Untitled

a guest
May 26th, 2019
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define PI 3.14159265
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. const ll N = 1005;
  7. const ld eps = 1e-4;
  8.  
  9. struct pd{
  10.     ld l,r;
  11.     ll id;
  12. };
  13.  
  14. ll n;
  15. ll x[N],y[N],r[N];
  16. vector <pd> angles;
  17.  
  18. bool cmp(pd prvi,pd drugi){
  19.     if(prvi.l == drugi.l){
  20.         return prvi.r < drugi.r;
  21.     }
  22.     return prvi.l < drugi.l;
  23. }
  24.  
  25. ld getangle(ld x,ld y){
  26.     if(abs(x) <= eps){
  27.         if(y > 0){
  28.             return ld(90);
  29.         }
  30.         return ld(270);
  31.     }
  32.     if(abs(y) <= eps){
  33.         if(x < 0){
  34.             return ld(180);
  35.         }
  36.         return ld(0);
  37.     }
  38.     if(x >= 0 && y >= 0){
  39.         return atan(abs(ld(y)/ld(x)))*180.0 / PI;
  40.     }
  41.     if(x <= 0 && y >= 0){
  42.         return 90.0 - atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(90);
  43.     }
  44.     if(x <= 0 && y <= 0){
  45.         return atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(180);
  46.     }
  47.     if(x >= 0 && y <= 0){
  48.         return 90.0 - atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(270);
  49.     }
  50. }
  51.  
  52. ld razl(ld a,ld b){
  53.     a -= b;
  54.     if(a < 0){
  55.         a += 2*PI;
  56.     }
  57.     return a;
  58. }
  59.  
  60. ld zbir(ld a,ld b){
  61.     a += b;
  62.     if(a >= 2*PI){
  63.         a -= 2*PI;
  64.     }
  65.     return a;
  66. }
  67.  
  68. ll sled(ll x){
  69.     x++;
  70.     if(x == n+1){
  71.         return 1;
  72.     }
  73.     return x;
  74. }
  75.  
  76. bool izmedju(ld levo,ld desno,ld stigo){
  77.     if(levo <= desno){
  78.         return (levo <= stigo && desno >= stigo);
  79.     }
  80.     else{
  81.         return ((levo <= stigo && stigo < 360) || (stigo <= desno));
  82.     }
  83. }
  84.  
  85. void solve(){
  86.     angles.clear();
  87.     for(int i = 1; i <= n; i++){
  88.         cin >> x[i] >> y[i] >> r[i];
  89.         if(x[i] == 0){
  90.             ld dd = sqrt(y[i]*y[i]-r[i]*r[i]);
  91.             ld visina = (dd*ld(r[i]))/y[i];
  92.             ld yo = sqrt(y[i]*y[i]-r[i]*r[i]-visina*visina);
  93.             if(y[i] < 0){
  94.                 yo = -yo;
  95.             }
  96.             ld x1 = visina,y1 = yo,x2 = -visina,y2 = yo;
  97.             angles.push_back({getangle(x1,y1),getangle(x2,y2),i});
  98.         }
  99.         else{
  100.             ld dx = x[i];
  101.             ld dy = y[i];
  102.             ld dd = sqrt(dx*dx+dy*dy);
  103.             ld tlen = sqrt(dx*dx+dy*dy-r[i]*r[i]);
  104.             ld a = asin(ld(r[i])/dd);
  105.             ld b = getangle(dx,dy)*PI / 180.0;
  106.             ld t = razl(b,a);
  107.             ld x1 = tlen*cos(t),y1 = tlen*sin(t);
  108.             t = zbir(b,a);
  109.             ld x2 = tlen*cos(t),y2 = tlen*sin(t);
  110.             angles.push_back({getangle(x1,y1),getangle(x2,y2),i});
  111.         }
  112.     }
  113.     sort(angles.begin(),angles.end(),cmp);
  114.     ld sol = 0;
  115.     for(int i = 1; i <= n; i++){
  116.         /// proveri da li je vidljiv
  117.         ld levo = angles[i-1].l,desno = angles[i-1].r;
  118.         ll koji = angles[i-1].id;
  119.         ld stigo = levo;
  120.         ll prvi = 0;
  121.         for(int j = 1; j <= n; j++){
  122.             if(j == i){
  123.                 continue;
  124.             }
  125.             ll ind = angles[j-1].id;
  126.             if(x[koji]*x[koji]+y[koji]*y[koji] < x[ind]*x[ind]+y[ind]*y[ind]){
  127.                 continue;
  128.             }
  129.             if(izmedju(angles[j-1].l,angles[j-1].r,levo)){
  130.                 prvi = j;
  131.                 break;
  132.             }
  133.         }
  134.         if(!prvi){
  135.             sol = max(sol,sqrt(ld(x[koji]*x[koji]+y[koji]*y[koji]))-ld(r[koji]));
  136.             continue;
  137.         }
  138.         bool bio = 0;
  139.         bool pokriven = 0;
  140.         for(int j = prvi; ; j=sled(j)){
  141.             if(izmedju(levo,stigo,desno)){
  142.                 pokriven = 1;
  143.                 break;
  144.             }
  145.             if(bio && j == prvi){
  146.                 break;
  147.             }
  148.             bio = 1;
  149.             if(j == i){
  150.                 continue;
  151.             }
  152.             ll ind = angles[j-1].id;
  153.             if(x[koji]*x[koji]+y[koji]*y[koji] < x[ind]*x[ind]+y[ind]*y[ind]){
  154.                 continue;
  155.             }
  156.            
  157.             if(izmedju(angles[j-1].l,angles[j-1].r,stigo)){
  158.                 stigo = angles[j-1].r;
  159.             }
  160.         }
  161.         if(!pokriven){
  162.             sol = max(sol,sqrt(ld(x[koji]*x[koji]+y[koji]*y[koji]))-ld(r[koji]));
  163.         }
  164.     }
  165.     cout << sol << endl;
  166. }
  167.  
  168. int main(){
  169.     cout.precision(3);
  170.     cout << fixed;
  171.     ios_base::sync_with_stdio(false);
  172.     cin.tie(0);
  173.     while(cin >> n && n){
  174.         solve();
  175.     }
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement