v 0. Pasted by slipstak2 as cpp at 2010-11-29 17:20:32 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 7.
  2. // 7D. Прямая и квадраты [sqline]
  3. // Решение за O(N*N)
  4. // ibelyaev: 26Nov2010
  5. #include <iostream>
  6. #include <cstdio>
  7.  
  8. using namespace std;
  9.  
  10. struct point
  11. {
  12.     int x,y;
  13.     point(){}
  14.     point(int X, int Y)
  15.     {
  16.         x = X;
  17.         y = Y;
  18.     }
  19. };
  20. double eps = 1e-8;
  21. double Fabs(double a)
  22. {
  23.     if (a<0)
  24.         return -a;
  25.     return a;
  26. }
  27. int Abs(int a)
  28. {
  29.     if (a<0)
  30.         return -a;
  31.     return a;
  32. }
  33. bool Equal(double a, double b)
  34. {
  35.     return Fabs(a-b) <= eps;
  36. }
  37. bool More(double a, double b)
  38. {
  39.     return a > b && !Equal(a,b);
  40. }
  41. struct line
  42. {
  43.     double a, b, c;
  44.     line(){}
  45.     line(point f, point s)
  46.     {
  47.         a = s.y - f.y;
  48.         b = f.x - s.x;
  49.         c = -a*f.x - b*f.y;
  50.     }
  51.     int getSign (int x, int y)
  52.     {
  53.         double value = a*x + b*y + c;
  54.         if (Equal(value, 0.0))
  55.             return 0;
  56.         else if (More(value, 0.0))
  57.             return 1;
  58.         else
  59.             return -1;
  60.     }
  61. };
  62. int n,w,e;
  63. void input()
  64. {
  65.     cin>>n>>w>>e;
  66. }
  67. void solve()
  68. {
  69.     line l(point(0,w),point(100*n,e));
  70.     int size = 100*n;
  71.     int amount = 0;
  72.     for (int i=0;i<size;i+=100)
  73.     {
  74.         for (int j=0;j<size;j+=100)
  75.         {
  76.             int res =
  77.             l.getSign(i    ,j) +
  78.             l.getSign(i+100,j) +
  79.             l.getSign(i    ,j+100) +
  80.             l.getSign(i+100,j+100);
  81.            
  82.             if (Abs(res) != 4)
  83.                 amount++;
  84.         }
  85.     }
  86.     cout<<amount;
  87. }
  88. int main()
  89. {
  90.     freopen("input.txt","r",stdin);
  91.     freopen("output.txt","w",stdout);
  92.    
  93.     input();
  94.     solve();
  95.     return 0;
  96. }


Editing is locked.