Advertisement
Malinovsky239

Untitled

Jan 23rd, 2012
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. #define eps (1e-6)
  7.  
  8. using namespace std;
  9.  
  10. typedef long long LL;
  11.  
  12. struct vect {
  13.     LL x, y;
  14.  
  15.     vect() {}
  16.  
  17.     vect(LL a, LL b) {
  18.         x = a, y = b;
  19.     }
  20.  
  21.     void read() {
  22.         cin >> x >> y;
  23.     }
  24. };
  25.  
  26. vect operator - (vect a, vect b) {
  27.     return vect(a.x - b.x, a.y - b.y);
  28. }
  29.  
  30. LL operator * (vect a, vect b) {
  31.     return a.x * b.x + a.y * b.y;
  32. }
  33.  
  34. LL rad, q, n, A, B, C;
  35. vect pos, vel;
  36.  
  37. bool check(LL x, LL y) {
  38.     if ((vect(x, y) - pos) * vel >= 0) {
  39.         if (abs(A * x + B * y + C) / sqrt(double(A * A + B * B)) * 1000 - rad - q > eps)
  40.             return false;
  41.         return true;
  42.     }
  43.     return false;
  44. }
  45.  
  46. LL count_segment(LL x1, LL x2, LL y) {
  47.     if (abs(x1) % 2 != y % 2)
  48.         x1++;
  49.     if (abs(x2) % 2 != y % 2)
  50.         x2--;
  51.    
  52.     if (x2 >= x1)
  53.         return (x2 - x1) / 2 + 1;
  54.     return 0;
  55. }
  56.  
  57. int main() {
  58.     freopen("spacepin.in", "r", stdin);
  59.     freopen("spacepin.out", "w", stdout);
  60.    
  61.     cin >> rad >> n >> q;
  62.     pos.read();
  63.     vel.read();
  64.  
  65.     A = vel.y, B = - vel.x;
  66.     C = - A * pos.x - B * pos.y;
  67.  
  68.     LL res = 0;
  69.     for (LL y = 0; y < n; y++) {
  70.         double x_mid = - double(B * y + C) / A;
  71.         LL x1 = LL(x_mid);     
  72.        
  73.         LL l = - y - 1, r = min(x1 + 1, y + 1);
  74.         LL mem_x1 = r - 1;
  75.  
  76.         while (l + 1 < r) {
  77.             LL mid = (l + r) / 2;
  78.             if (check(mid, y))
  79.                 r = mid;
  80.             else
  81.                 l = mid;                                                             
  82.         }
  83.         res += count_segment(r, mem_x1, y);    
  84.  
  85.         l = max(x1, - y - 1), r = y + 1;
  86.         LL mem_l = l + 1;
  87.         while (l + 1 < r) {
  88.             LL mid = (l + r) / 2;
  89.             if (check(mid, y))
  90.                 l = mid;
  91.             else
  92.                 r = mid;                                                             
  93.         }
  94.         res += count_segment(mem_l, l, y);     
  95.     }
  96.  
  97.     cout << res << endl;
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement