Dang_Quan_10_Tin

SAFEGUARD (Không nằm trên biên)

Aug 2nd, 2021
778
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.     int id;
  30.     Point(ll x = 0, ll y = 0) : x(x), y(y) {}
  31.     Point operator-(const Point &a) const
  32.     {
  33.         return Point(x - a.x, y - a.y);
  34.     }
  35.     bool operator<(const Point &a) const
  36.     {
  37.         return x < a.x || (x == a.x && y < a.y);
  38.     }
  39.     ll operator*(const Point &a) const
  40.     {
  41.         return x * a.y - y * a.x;
  42.     }
  43.     ll len()
  44.     {
  45.         return x * x + y * y;
  46.     }
  47.     ll operator&(const Point &a) const
  48.     {
  49.         return x * a.x + y * a.y;
  50.     }
  51.     bool operator==(const Point &a) const
  52.     {
  53.         return x == a.x && y == a.y;
  54.     }
  55. } a[N], b[N];
  56.  
  57. int n, m, l;
  58. bool ans[N];
  59.  
  60. void Read()
  61. {
  62.  
  63.     //read(n);
  64.     cin >> n;
  65.     for (int i = 1; i <= n; ++i)
  66.         //read(a[i].x), read(a[i].y);
  67.         cin >> a[i].x >> a[i].y;
  68.     //read(m);
  69.     cin >> m;
  70.     for (int i = 1; i <= m; ++i)
  71.         //read(b[i].x), read(b[i].y),
  72.         cin >> b[i].x >> b[i].y, b[i].id = i;
  73.     l = m;
  74. }
  75.  
  76. void ConvexHull()
  77. {
  78.     sort(a + 1, a + n + 1);
  79.     sort(a + 2, a + n + 1, [&](const Point &x, const Point &y)
  80.          {
  81.              Point u = x - a[1],
  82.                    v = y - a[1];
  83.              return u * v > 0 || (u * v == 0 && u.len() < v.len());
  84.          });
  85.     vector<Point> s;
  86.     s.reserve(n);
  87.     a[n + 1] = a[1];
  88.     for (int i = 1; i <= n + 1; ++i)
  89.     {
  90.         while (s.size() > 2 && (a[i] - s[s.size() - 2]) * (s.back() - s[s.size() - 2]) >= 0)
  91.             s.pop_back();
  92.         s.emplace_back(a[i]);
  93.     }
  94.  
  95.     s.pop_back();
  96.  
  97.     n = s.size();
  98.     for (int i = 1; i <= n; ++i)
  99.         a[i] = s[i - 1];
  100. }
  101.  
  102. void Sub_2()
  103. {
  104.     ConvexHull();
  105.  
  106.     //for (int i = 1; i <= n; ++i)
  107.     //    cout << i << ": " << a[i].x << " " << a[i].y << '\n';
  108.  
  109.     sort(b + 1, b + m + 1, [&](const Point &x, const Point &y)
  110.          { return x.x > y.x || (x.x == y.x && x.y > y.y); });
  111.  
  112.     while (m && (b[m].x < a[1].x || (b[m].x == a[1].x && b[m].y <= a[1].y)))
  113.         --m;
  114.  
  115.     sort(b + 1, b + m + 1, [&](const Point &x, const Point &y)
  116.          {
  117.              Point u = x - a[1],
  118.                    v = y - a[1];
  119.              return u * v > 0 || (u * v == 0 && u.len() < v.len());
  120.          });
  121.  
  122.     a[0] = a[n];
  123.     a[n + 1] = a[1];
  124.  
  125.     for (int i = 1, j = 2; i <= m; ++i)
  126.     {
  127.         while (j <= n && (a[j] - a[1]) * (b[i] - a[1]) >= 0)
  128.             ++j;
  129.  
  130.         Point u = a[j - 1] - b[i],
  131.               v = a[j] - b[i];
  132.         if (u * v > 0 && (j > 3 || (a[1] - b[i]) * (a[2] - b[i]) > 0))
  133.             ans[b[i].id] = 1;
  134.  
  135.         //cout << i << ":: " << j << " " << b[i].x << " " << b[i].y << " " << u * v << "\n";
  136.     }
  137.  
  138.     for (int i = 1; i <= l; ++i)
  139.         cout << (ans[i] ? "YES\n" : "NO\n");
  140. }
  141.  
  142. int32_t main()
  143. {
  144.     ios::sync_with_stdio(0);
  145.     cin.tie(0);
  146.     cout.tie(0);
  147.     if (fopen(task ".INP", "r"))
  148.     {
  149.         freopen(task ".INP", "r", stdin);
  150.         freopen(task ".OUT", "w", stdout);
  151.     }
  152.     Read();
  153.     Sub_2();
  154. }
RAW Paste Data