# 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!
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>
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.
61. {
62.
64.     cin >> n;
65.     for (int i = 1; i <= n; ++i)
67.         cin >> a[i].x >> a[i].y;
69.     cin >> m;
70.     for (int i = 1; i <= m; ++i)
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);