# SAFEGUARD (Chỉ trên biên)

Aug 2nd, 2021
729
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.     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.
59. {
61.     for (int i = 1; i <= n; ++i)
64.     for (int i = 1; i <= m; ++i)
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 && (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);