Advertisement
hkshakib

Untitled

Jul 16th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int gcd(int a, int b, int &x, int &y)
  5. {
  6. if (a == 0)
  7. {
  8. x = 0;
  9. y = 1;
  10. return b;
  11. }
  12. int x1, y1;
  13. int d = gcd(b%a, a, x1, y1);
  14. x = y1 - (b / a) * x1;
  15. y = x1;
  16. return d;
  17. }
  18.  
  19. bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g)
  20. {
  21. g = gcd(abs(a), abs(b), x0, y0);
  22. if (c % g)
  23. {
  24. return false;
  25. }
  26. x0 *= c / g;
  27. y0 *= c / g;
  28. if (a < 0)
  29. x0 = -x0;
  30. if (b < 0)
  31. y0 = -y0;
  32. return true;
  33. }
  34. void shift_solution(int & x, int & y, int a, int b, int cnt)
  35. {
  36. x += cnt * b;
  37. y -= cnt * a;
  38. }
  39.  
  40. int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy)
  41. {
  42. int x, y, g;
  43. if (!find_any_solution(a, b, c, x, y, g))
  44. return 0;
  45. a /= g;
  46. b /= g;
  47.  
  48. int sign_a = a > 0 ? +1 : -1;
  49. int sign_b = b > 0 ? +1 : -1;
  50.  
  51. shift_solution(x, y, a, b, (minx - x) / b);
  52. if (x < minx)
  53. shift_solution(x, y, a, b, sign_b);
  54. if (x > maxx)
  55. return 0;
  56. int lx1 = x;
  57.  
  58. shift_solution(x, y, a, b, (maxx - x) / b);
  59. if (x > maxx)
  60. shift_solution(x, y, a, b, -sign_b);
  61. int rx1 = x;
  62.  
  63. shift_solution(x, y, a, b, -(miny - y) / a);
  64. if (y < miny)
  65. shift_solution(x, y, a, b, -sign_a);
  66. if (y > maxy)
  67. return 0;
  68. int lx2 = x;
  69.  
  70. shift_solution(x, y, a, b, -(maxy - y) / a);
  71. if (y > maxy)
  72. shift_solution(x, y, a, b, sign_a);
  73. int rx2 = x;
  74.  
  75. if (lx2 > rx2)
  76. swap(lx2, rx2);
  77. int lx = max(lx1, lx2);
  78. int rx = min(rx1, rx2);
  79.  
  80. if (lx > rx)
  81. return 0;
  82. return (rx - lx) / abs(b) + 1;
  83. }
  84. int main()
  85. {
  86. int a,b,c,x1,x2,y1,y2;
  87. cin>>a>>b>>c>>x1>>x2>>y1>>y2;
  88. cout<<find_all_solutions(a,b,c,x1,x2,y1,y2)<<endl;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement