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

Paste will expire never.

  1. // Меньшиков. Тренировка 7.
  2. // 7D. Прямая и квадраты [sqline]
  3. // Решение за O(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. struct line
  21. {
  22.     double a,b,c;
  23.     line(){}
  24.     line(point f, point s)
  25.     {
  26.         a = s.y - f.y;
  27.         b = f.x - s.x;
  28.         c = -a * f.x -b * f.y;
  29.     }
  30.     double getY(double x)
  31.     {
  32.         return (-a*x - c) / b;
  33.     }
  34. };
  35. int N, W, E;
  36. void input()
  37. {
  38.     cin>>N>>W>>E;
  39. }
  40. const double eps = 1e-8;
  41. double fabs(double a)
  42. {
  43.     if (a<0)
  44.         return -a;
  45.     return a;
  46. }
  47. bool Equal(double a, double b)
  48. {
  49.     return fabs(a-b) <= eps;
  50. }
  51. bool Less(double a, double b)
  52. {
  53.     return (a < b && !Equal(a,b));
  54. }
  55. bool More(double a, double b)
  56. {
  57.     return (a > b && !Equal(a,b));
  58. }
  59. // a - положительное, поэтому корректировать +eps
  60. bool isRoundDoulbe(double &a)
  61. {
  62.     //return a == (int)a; // может быть потеря точности double
  63.     return fabs(a - (int)(a + eps)) <= eps;
  64. }
  65. // curY - находится на краю области и не является углом
  66. // curY - нормированная величина (Y/100)
  67. bool isSideNoCornerY(int curY)
  68. {
  69.     return curY !=0 && curY != N;
  70. }
  71. void solve()
  72. {
  73.     line l(point(0,W),point(100*N, E));
  74.     // горизонтальная линия
  75.     if (l.a == 0)
  76.     {
  77.         if (W%100 == 0 && W!=0 && W != 100*N)
  78.             cout<<2*N;
  79.         else
  80.             cout<<N;
  81.         return;
  82.     }
  83.    
  84.     int crossRect = 0;
  85.     int y = W;
  86.     double prevY = l.getY(0) / 100;
  87.  
  88.     // начальная точка пересекает два прямогоульника
  89.     // один из них считаем сразу(верхний или нижний)
  90.     // второй во время первой итерации цикла
  91.     if (isRoundDoulbe(prevY) && isSideNoCornerY(prevY))
  92.         crossRect++;
  93.  
  94.     for (int x=1; x<=N;x++)
  95.     {
  96.         double curY = l.getY(100*x) / 100;
  97.         if (isRoundDoulbe(curY))
  98.         {
  99.             if (x != N) // крестовина
  100.                 crossRect += 2;// диагональные квадраты
  101.             else if (isSideNoCornerY(curY)) // квадрат снизу или сверху
  102.                 crossRect++;
  103.         }
  104.         if ((int)(curY + eps) != (int)(prevY + eps))
  105.         {
  106.             // убывающая линия
  107.             if (More(prevY,curY)&& !isRoundDoulbe(prevY))
  108.                 crossRect++; // нижний квадрат
  109.             // возрастающая линия
  110.             if (Less(prevY,curY) && !isRoundDoulbe(curY))
  111.                 crossRect++; // верхний квадрат
  112.         }
  113.         crossRect++; // текущий квадрат
  114.         prevY = curY;
  115.     }
  116.     cout<<crossRect;
  117. }
  118. int main()
  119. {
  120.     freopen("input.txt","r",stdin);
  121.     freopen("output.txt","w",stdout);
  122.    
  123.     input();
  124.     solve();
  125.     return 0;
  126. }


Editing is locked.