Advertisement
Guest User

Untitled

a guest
Oct 27th, 2013
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. //Lasha Bukhnikashvili
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<math.h>
  5. #include<iomanip>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<queue>
  10. #include<string>
  11. #define Pi 3.14159265358
  12. #define mod9 %1000000009
  13. #define INF 1000000000
  14. #define mod7 1000000007
  15. #define LL  long long
  16. #define time clock()/(double)CLOCKS_PER_SEC
  17. using namespace std;
  18.  
  19.   long long m,lx,p,q,rx,mid,n,ra,i,j;
  20.   long double l,r,ind,ans,c[3000001],x[3000001];
  21. int main(){
  22.    
  23.      cin>>m>>n>>ra;
  24.      for (i=1;i<=m;i++)
  25.         cin>>c[i];
  26.     for (i=1;i<=n;i++)
  27.         cin>>x[i];
  28.     ind=c[1];
  29.     for (i=1;i<=n;i++){
  30.         l=x[i]-sqrt(ra*ra-1); r=x[i]+sqrt(ra*ra+1);
  31.         lx=1; rx=m;
  32.         while (lx<rx){
  33.             mid=(lx+rx)/2;
  34.             if (c[mid]<l) lx=mid+1; else rx=mid;
  35.         };    
  36.         p=lx;
  37.         lx=1; rx=m;
  38.         while (lx<rx){
  39.             if (rx-lx==1){
  40.                 if (c[rx]<=r) lx=rx; else rx=lx;
  41.                 break;
  42.             };
  43.             mid=(lx+rx)/2;
  44.             if (c[mid]<=r) lx=mid; else rx=mid-1;
  45.         };  
  46.         q=lx;
  47.         if (ind>=c[p] && ind<=c[q]) continue;
  48.         if (ind<c[p]) ans+=c[p]-ind,ind=c[p];
  49.          else ans+=ind-c[q],ind=c[q];
  50.     };
  51.     cout<<fixed<<setprecision(1)<<ans;
  52.  return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement