Dang_Quan_10_Tin

KHÁC PHÍA

Nov 1st, 2022
1,023
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. template <class T>
  9. void read(T &x)
  10. {
  11.     x = 0;
  12.     register int c;
  13.     while ((c = getchar()) && (c > '9' || c < '0'))
  14.         ;
  15.     for (; c >= '0' && c <= '9'; c = getchar())
  16.         x = x * 10 + c - '0';
  17. }
  18.  
  19. constexpr bool typetest = 0;
  20. constexpr int N = 2e5 + 5;
  21. constexpr ll mod = 1e9 + 7;
  22.  
  23. struct Vector
  24. {
  25.     ll x, y;
  26.     Vector(ll x = 0, ll y = 0) : x(x), y(y) {}
  27.     Vector operator-(const Vector &a) const
  28.     {
  29.         return Vector(x - a.x, y - a.y);
  30.     }
  31.  
  32.     ll operator*(const Vector &a) const
  33.     {
  34.         return x * a.y - y * a.x;
  35.     }
  36. } d[N];
  37.  
  38. using Point = Vector;
  39.  
  40. int n;
  41. ll a, b, c;
  42.  
  43. void Read()
  44. {
  45.     cin >> n >> a >> b >> c;
  46.  
  47.     for (int i = 1; i <= n; ++i)
  48.         cin >> d[i].x >> d[i].y;
  49. }
  50.  
  51. // ax + by = c
  52. // a * x1 + b * y1 = a
  53. // a * x2 + b * y2 = b
  54.  
  55. pair<ll, ll> Dio(ll a, ll b, ll c)
  56. {
  57.     ll xa = 1, ya = 0, xb = 0, yb = 1, xr, yr, r;
  58.  
  59.     while (b != 0)
  60.     {
  61.         ll q = a / b;
  62.  
  63.         r = a - b * q;
  64.         xr = xa - xb * q;
  65.         yr = ya - yb * q;
  66.  
  67.         a = b;
  68.         xa = xb;
  69.         ya = yb;
  70.  
  71.         b = r;
  72.         xb = xr;
  73.         yb = yr;
  74.     }
  75.  
  76.     // d -> gcd(a, b)
  77.     // a * xd + b * yd = gcd(a, b)
  78.     // a * (xd * c/gcd(a, b)) + b * (yd * c/gcd(a, b)) = c;
  79.  
  80.     ll v = c / a;
  81.  
  82.     return make_pair(xa * v, ya * v);
  83. }
  84.  
  85. void Solve()
  86. {
  87.     pair<ll, ll> point = Dio(a, b, -c);
  88.  
  89.     Point u = Point(point.first, point.second);
  90.     Point v = Point(u.x + b, u.y - a);
  91.  
  92.     ll cnt[2] = {0, 0};
  93.  
  94.     for (int i = 1; i <= n; ++i)
  95.         if ((d[i] - u) * (v - d[i]) > 0)
  96.             ++cnt[0];
  97.         else if ((d[i] - u) * (v - d[i]) < 0)
  98.             ++cnt[1];
  99.  
  100.     cout << cnt[0] * cnt[1];
  101. }
  102.  
  103. int32_t main()
  104. {
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     cout.tie(0);
  108.  
  109.     if (fopen("tests.inp", "r"))
  110.     {
  111.         freopen("test.inp", "r", stdin);
  112.         freopen("test.out", "w", stdout);
  113.     }
  114.  
  115.     int t(1);
  116.     if (typetest)
  117.         cin >> t;
  118.  
  119.     for (int _ = 1; _ <= t; ++_)
  120.     {
  121.         // cout << "Case #" << _ << endl;
  122.         Read();
  123.         Solve();
  124.     }
  125.     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  126. }
  127.  
  128. /*
  129.  
  130. */
  131.  
  132. /*
  133. Input:
  134. 4 5 4
  135. 2 3
  136. 2 5
  137. 3 1
  138. 4 4
  139.  
  140. Output:
  141. 9
  142. */
Advertisement
Add Comment
Please, Sign In to add comment