Advertisement
DuongNhi99

SAFEGUARD

Jan 7th, 2022
662
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ld = long double;
  6. using pii = pair<int, int>;
  7.  
  8. const int maxN = 1e5 + 5;
  9. const int INF = 1e9 + 7;
  10. const ld eps = 1e-8;
  11.  
  12. struct point {
  13.     long long x, y;
  14. };
  15.  
  16. bool xetx(point a, point b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); }
  17. bool xety(point a, point b) { return (a.y < b.y) || (a.y == b.y && a.x < b.x); }
  18.  
  19. bool CW(point a, point b, point c) { // Cùng chiều kim đồng hồ
  20.     return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) > 0;
  21. }
  22.  
  23. bool CCW(point a, point b, point c) { // Ngược chiều kim đồng hồ
  24.     return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) < 0;
  25. }
  26.  
  27. int fEqual(double a, double b) {
  28.   return (fabs(a - b) < eps) ? 1 : 0;
  29. }
  30.  
  31. int n, k;
  32. vector<point> Points;
  33.  
  34. vector<point> hull;
  35.  
  36. void CONVEXHULL(vector<point> &a) {
  37.     if (a.size() == 1)
  38.         return;
  39.  
  40.     sort (a.begin(), a.end(), &xetx);
  41.  
  42.     point p1 = a[0], p2 = a.back();
  43.  
  44.     vector<point> up, down;
  45.     up.push_back(p1);
  46.     down.push_back(p1);
  47.  
  48.     for (size_t i = 1; i < a.size(); ++i) {
  49.         if (i == a.size()-1 || CW(p1, a[i], p2)) {
  50.             while (up.size() >= 2 && !CW(up[up.size()-2], up[up.size()-1], a[i]))
  51.                 up.pop_back();
  52.             up.push_back(a[i]);
  53.         }
  54.  
  55.         if (i == a.size()-1 || CCW(p1, a[i], p2)) {
  56.             while (down.size() >= 2 && !CCW(down[down.size()-2], down[down.size()-1], a[i]))
  57.                 down.pop_back();
  58.             down.push_back(a[i]);
  59.         }
  60.     }
  61.  
  62.     a.clear();
  63.     for (int i = 0; i < down.size()-1; ++i)
  64.         a.push_back(down[i]);
  65.     for (int i = up.size()-1; i > 0; --i)
  66.         a.push_back(up[i]);
  67.  
  68.     long long ans = a.size();
  69.     long long mx = INF, my = INF, id = -1;
  70.     for (int i = 0; i < ans; ++i)
  71.         my = min(my, a[i].y);
  72.     for (int i = 0; i < ans; ++i)
  73.         if (a[i].y == my && a[i].x < mx)
  74.             mx = a[i].x, id = i;
  75.     hull.resize(ans);
  76.     for (int i = 0; i < ans; ++i) {
  77.         hull[i] = a[id%ans];
  78.         ++id;
  79.     }
  80. }
  81.  
  82. bool check(point &p) {
  83.     if (hull.size() < 3)
  84.         return false;
  85.     int l = 1, r = hull.size() - 1;
  86.  
  87.     if (CCW(hull[0], hull[l], hull[r]))
  88.         swap(l, r);
  89.  
  90.     if (CCW(hull[0], hull[l], p) || CW(hull[0], hull[r], p))
  91.         return false;
  92.  
  93.     while (abs(r - l) > 1) {
  94.         int m = (l + r) / 2;
  95.  
  96.         if (CW(hull[0], hull[m], p))
  97.             l = m;
  98.         else
  99.             r = m;
  100.     }
  101.  
  102.     if (CCW(hull[l], hull[r], p)) return false;
  103.     return true;
  104. }
  105.  
  106. long long ans = 0;
  107.  
  108. int main() {
  109. #ifdef LOCAL
  110.     freopen("in1.txt", "r", stdin);
  111. #else
  112.     freopen("SAFEGUARD.inp", "r", stdin);
  113.     freopen("SAFEGUARD.out", "w", stdout);
  114. #endif
  115.     ios_base::sync_with_stdio(false);
  116.     cin.tie(nullptr);
  117.  
  118.     cin >> n;
  119.     for (int i = 0; i < n; i++) {
  120.         point a; cin >> a.x >> a.y;
  121.         Points.push_back(a);
  122.     }
  123.  
  124.     CONVEXHULL(Points);
  125.  
  126.     cin >> k;
  127.     for (int i = 1; i <= k; ++i) {
  128.         point p; cin >> p.x >> p .y;
  129.         ans += check(p);
  130.     }
  131.     cout << ans << '\n';
  132.  
  133.     return 0;
  134. }
  135.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement