Advertisement
SuitNdtie

Springer

May 29th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<cmath>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. struct circle{
  7.     double pos;
  8.     double rad;
  9. };
  10.  
  11. struct square{
  12.     double L;
  13.     double R;
  14. /*  double lenght;
  15.     double width;*/
  16. };
  17.  
  18. double callenght(double r,double w){
  19.     return sqrt((r*r)-(w*w));
  20. }
  21.  
  22. bool Lcmp(square a,square b){
  23.     return a.L < b.L;
  24. }
  25.  
  26. double max(double a,double b){
  27.     return (a > b ? a : b);
  28. }
  29.  
  30. int main()
  31. {
  32.     int n;
  33.     double l,w;
  34.     scanf("%d %lf %lf",&n,&l,&w);
  35.    
  36.     circle Carr[n];
  37.     for(int i = 0 ; i < n ; i ++){
  38.         scanf("%lf %lf",&Carr[i].pos,&Carr[i].rad);
  39.     }
  40.     int sn = 0;
  41.     square Sarr[n];
  42.     for(int i = 0 ; i < n ; i ++){
  43.         double pos = Carr[i].pos;
  44.         double rad = Carr[i].rad;
  45.         if(rad*2 + 1 < w)continue;
  46.         double lenght = callenght(2*rad,w);
  47.     //  printf("Test converse to square #%d (%.0lf,%.0lf) -> %lf -> [%lf,%lf]\n",i,pos,rad,lenght,pos - lenght/2 , pos + lenght/2);
  48.         Sarr[sn++] = {pos - lenght/2 , pos + lenght/2};
  49.     }
  50.     sort(Sarr,Sarr+sn,Lcmp);
  51.     double maxR = 0;
  52.     double nxtR = -1;
  53.     int ans = 0;
  54.     for(int i = 0 ; i < sn ; ){
  55.         double L = Sarr[i].L;
  56.         double R = Sarr[i].R;
  57.     //  printf("#%d : %lf %lf\n",i,L,R);
  58.         if(R < 0)continue;
  59.         if(L > l)break;
  60.         if(L <= maxR){
  61.             nxtR = max(nxtR , R);
  62.             i ++;
  63.         }
  64.         else{
  65.             if(nxtR == -1){
  66.                 printf("-1");
  67.                 return 0;
  68.             }
  69.             ans++;
  70.             maxR = max(maxR,nxtR);
  71.         //  if(maxR > l)break;
  72.         //  printf("up to %lf\n",maxR);
  73.             nxtR = -1;
  74.         }
  75.     }
  76.     if(maxR < l && nxtR > maxR){
  77.         maxR = nxtR;
  78.         ans++;
  79.     }
  80.     if(maxR < l){
  81.         printf("-1");
  82.         return 0;
  83.     }
  84.     printf("%d",ans);
  85.     return 0;
  86. }
  87. /*
  88. 3 8 0
  89. 2 3
  90. 4 2
  91. 7 2
  92.  
  93. 3 5 0
  94. 1 1
  95. 2 1
  96. 4 1
  97.  
  98.  
  99. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement