Dang_Quan_10_Tin

SAFEGUARD

Aug 2nd, 2021
626
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "SAFEGUARD"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. using ll = long long;
  12. using ld = long double;
  13.  
  14. template <class T>
  15. void read(T &x)
  16. {
  17.     x = 0;
  18.     register int c;
  19.     while ((c = getchar()) && (c > '9' || c < '0'))
  20.         ;
  21.     for (; c >= '0' && c <= '9'; c = getchar())
  22.         x = x * 10 + c - '0';
  23. }
  24.  
  25. constexpr int N = 1e5 + 5;
  26. struct Point
  27. {
  28.     ll x, y;
  29.     Point(ll x = 0, ll y = 0) : x(x), y(y) {}
  30.     Point operator-(const Point &a) const
  31.     {
  32.         return Point(x - a.x, y - a.y);
  33.     }
  34.     bool operator<(const Point &a) const
  35.     {
  36.         return x < a.x || (x == a.x && y < a.y);
  37.     }
  38.     ll operator*(const Point &a) const
  39.     {
  40.         return x * a.y - y * a.x;
  41.     }
  42.     ll len()
  43.     {
  44.         return x * x + y * y;
  45.     }
  46.     ll operator&(const Point &a) const
  47.     {
  48.         return x * a.x + y * a.y;
  49.     }
  50.     bool operator==(const Point &a) const
  51.     {
  52.         return x == a.x && y == a.y;
  53.     }
  54. } a[N], b[N];
  55.  
  56. int n, m;
  57.  
  58. void Read()
  59. {
  60.     read(n);
  61.     for (int i = 1; i <= n; ++i)
  62.         read(a[i].x), read(a[i].y);
  63.     read(m);
  64.     for (int i = 1; i <= m; ++i)
  65.         read(b[i].x), read(b[i].y);
  66. }
  67.  
  68. void ConvexHull()
  69. {
  70.     sort(a + 1, a + n + 1);
  71.     sort(a + 2, a + n + 1, [&](const Point &x, const Point &y)
  72.          {
  73.              Point u = x - a[1],
  74.                    v = y - a[1];
  75.              return u * v > 0 || (u * v == 0 && u.len() < v.len());
  76.          });
  77.     vector<Point> s;
  78.     s.reserve(n);
  79.     a[n + 1] = a[1];
  80.     for (int i = 1; i <= n + 1; ++i)
  81.     {
  82.         while (s.size() > 2 && (a[i] - s[s.size() - 2]) * (s.back() - s[s.size() - 2]) >= 0)
  83.             s.pop_back();
  84.         s.emplace_back(a[i]);
  85.     }
  86.  
  87.     s.pop_back();
  88.  
  89.     n = s.size();
  90.     for (int i = 1; i <= n; ++i)
  91.         a[i] = s[i - 1];
  92. }
  93.  
  94. ll Size(Point a[N], int n)
  95. {
  96.     ll ans(0);
  97.     for (int i = 1; i < n; ++i)
  98.         ans += a[i] * a[i + 1];
  99.     ans += a[n] * a[1];
  100.     return abs(ans);
  101. }
  102.  
  103. void Sub_1()
  104. {
  105.     ConvexHull();
  106.     ll S = Size(a, n);
  107.     if (Size(a, n) == 0)
  108.     {
  109.         cout << 0;
  110.         return;
  111.     }
  112.  
  113.     int ans(0);
  114.  
  115.     for (int i = 1; i <= m; ++i)
  116.     {
  117.         ll tmp(0);
  118.         for (int j = 1; j < n; ++j)
  119.             tmp += abs((a[j] - b[i]) * (a[j + 1] - b[i]));
  120.         tmp += abs((a[n] - b[i]) * (a[1] - b[i]));
  121.  
  122.         if (S == tmp)
  123.             ++ans;
  124.     }
  125.  
  126.     cout << ans;
  127. }
  128.  
  129. void Sub_2()
  130. {
  131.     ConvexHull();
  132.  
  133.     //for (int i = 1; i <= n; ++i)
  134.     //    cout << a[i].x << " " << a[i].y << "\n";
  135.  
  136.     int ans(0);
  137.     if (Size(a, n) == 0)
  138.     {
  139.         cout << 0;
  140.         return;
  141.     }
  142.     sort(b + 1, b + m + 1, [&](const Point &x, const Point &y)
  143.          { return x.x > y.x || (x.x == y.x && x.y > y.y); });
  144.  
  145.     while (m && (b[m].x < a[1].x || (b[m].x == a[1].x && b[m].y <= a[1].y)))
  146.         ans += b[m].x == a[1].x && b[m].y == a[1].y,
  147.             --m;
  148.  
  149.     sort(
  150.         b + 1, b + m + 1, [&](const Point &x, const Point &y)
  151.         {
  152.             Point u = x - a[1],
  153.                   v = y - a[1];
  154.             return u * v > 0 || (u * v == 0 && u.len() < v.len());
  155.         });
  156.  
  157.     a[0] = a[n];
  158.     a[n + 1] = a[1];
  159.  
  160.     for (int i = 1, j = 2; i <= m; ++i)
  161.     {
  162.         while (j <= n && (a[j] - a[1]) * (b[i] - a[1]) >= 0)
  163.             ++j;
  164.  
  165.         //cout << (a[2] - a[1]) * (b[i] - a[1]) << "\n";
  166.  
  167.         Point u = a[j - 1] - b[i],
  168.               v = a[j] - b[i];
  169.  
  170.         if (u * v > 0 || (u * v == 0 && (b[i] == a[j] || b[i] == a[j - 1] || (u & v) < 0)))
  171.             ++ans;
  172.  
  173.         //cout << i << ": " << j << " --- " << b[i].x << " " << b[i].y << " --- " << ans << '\n';
  174.     }
  175.  
  176.     cout << ans;
  177. }
  178.  
  179. int32_t main()
  180. {
  181.     ios::sync_with_stdio(0);
  182.     cin.tie(0);
  183.     cout.tie(0);
  184.     if (fopen(task ".INP", "r"))
  185.     {
  186.         freopen(task ".INP", "r", stdin);
  187.         freopen(task ".OUT", "w", stdout);
  188.     }
  189.     Read();
  190.     //if (1ll * m * n <= 2e7)
  191.     //    Sub_1();
  192.     //else
  193.     Sub_2();
  194. }
  195.  
RAW Paste Data