Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using pii = pair<int, int>;
- const int maxN = 1e5 + 5;
- const int INF = 1e9 + 7;
- const ld eps = 1e-8;
- struct point {
- long long x, y;
- };
- bool xetx(point a, point b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); }
- bool xety(point a, point b) { return (a.y < b.y) || (a.y == b.y && a.x < b.x); }
- bool CW(point a, point b, point c) { // Cùng chiều kim đồng hồ
- return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) > 0;
- }
- bool CCW(point a, point b, point c) { // Ngược chiều kim đồng hồ
- return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) < 0;
- }
- int fEqual(double a, double b) {
- return (fabs(a - b) < eps) ? 1 : 0;
- }
- int n, k;
- vector<point> Points;
- vector<point> hull;
- void CONVEXHULL(vector<point> &a) {
- if (a.size() == 1)
- return;
- sort (a.begin(), a.end(), &xetx);
- point p1 = a[0], p2 = a.back();
- vector<point> up, down;
- up.push_back(p1);
- down.push_back(p1);
- for (size_t i = 1; i < a.size(); ++i) {
- if (i == a.size()-1 || CW(p1, a[i], p2)) {
- while (up.size() >= 2 && !CW(up[up.size()-2], up[up.size()-1], a[i]))
- up.pop_back();
- up.push_back(a[i]);
- }
- if (i == a.size()-1 || CCW(p1, a[i], p2)) {
- while (down.size() >= 2 && !CCW(down[down.size()-2], down[down.size()-1], a[i]))
- down.pop_back();
- down.push_back(a[i]);
- }
- }
- a.clear();
- for (int i = 0; i < down.size()-1; ++i)
- a.push_back(down[i]);
- for (int i = up.size()-1; i > 0; --i)
- a.push_back(up[i]);
- long long ans = a.size();
- long long mx = INF, my = INF, id = -1;
- for (int i = 0; i < ans; ++i)
- my = min(my, a[i].y);
- for (int i = 0; i < ans; ++i)
- if (a[i].y == my && a[i].x < mx)
- mx = a[i].x, id = i;
- hull.resize(ans);
- for (int i = 0; i < ans; ++i) {
- hull[i] = a[id%ans];
- ++id;
- }
- }
- bool check(point &p) {
- if (hull.size() < 3)
- return false;
- int l = 1, r = hull.size() - 1;
- if (CCW(hull[0], hull[l], hull[r]))
- swap(l, r);
- if (CCW(hull[0], hull[l], p) || CW(hull[0], hull[r], p))
- return false;
- while (abs(r - l) > 1) {
- int m = (l + r) / 2;
- if (CW(hull[0], hull[m], p))
- l = m;
- else
- r = m;
- }
- if (CCW(hull[l], hull[r], p)) return false;
- return true;
- }
- long long ans = 0;
- int main() {
- #ifdef LOCAL
- freopen("in1.txt", "r", stdin);
- #else
- freopen("SAFEGUARD.inp", "r", stdin);
- freopen("SAFEGUARD.out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int i = 0; i < n; i++) {
- point a; cin >> a.x >> a.y;
- Points.push_back(a);
- }
- CONVEXHULL(Points);
- cin >> k;
- for (int i = 1; i <= k; ++i) {
- point p; cin >> p.x >> p .y;
- ans += check(p);
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement