MinhNGUYEN2k4

Untitled

Sep 24th, 2021
714
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define double long double
  4. #define Task "NEWCARO"
  5. #define READFILE freopen(Task".inp", "r", stdin)
  6. #define WRITEFILE freopen(Task".out", "w", stdout)
  7. #define double long double
  8. #define oo 0x3f3f3f3f3f
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define X first
  13. #define Y second
  14. #define watch(x) cout << (#x) << " = " << x << endl
  15. #define debug(x) cout << (#x) << " = " << x << endl
  16. #define all(x) x.begin(), x.end()
  17. #define sz(x) x.size()
  18. #define endl '\n'
  19. #define max3(a,b,c) max(max(a, b), c)
  20. #define max4(a,b,c,d) max(max(a, b), max(c, d))
  21. #define min4(a,b,c,d) min(min(a, b), min(c, d))
  22. #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
  23. #define ever (;true;)
  24. #define maxn 505
  25.  
  26. #define PI 3.14159265
  27.  
  28. using namespace std;
  29.  
  30. typedef pair < int, int > ii;
  31. typedef pair < int, ii > iii;
  32. typedef pair < ii, ii > iiii;
  33. typedef vector < int > vi;
  34. typedef vector < ii > vii;
  35. typedef vector < vi > vvi;
  36. typedef vector < iii > viii;
  37. typedef vector < vii > vvii;
  38. typedef vector < iiii > viiii;
  39. typedef vector < vvi > vvvi;
  40.  
  41. const int N = 5e4 + 5;
  42.  
  43. int n;
  44. ii a[N], b[N];
  45. ii st[N];
  46. int h = 0;
  47.  
  48. void init(){
  49.     FAST;
  50.     #ifndef ONLINE_JUDGE
  51.     READFILE;
  52.     WRITEFILE;
  53.     #endif // ONLINE_JUDGE
  54.     cin >> n;
  55.     for (int i = 1; i <= n; ++i){
  56.         cin >> a[i].X >> a[i].Y;
  57.     }
  58.     for (int i = 1; i <= n; ++i){
  59.         cin >> b[i].X >> b[i].Y;
  60.     }
  61. }
  62.  
  63. ii operator - (const ii &a, const ii &b){
  64.     return ii(a.X - b.X, a.Y - b.Y);
  65. }
  66.  
  67. int CCW(ii u, ii v){
  68.     int T = u.X * v.Y - u.Y * v.X;
  69.     if (T > 0) return 1;
  70.     if (T < 0) return -1;
  71.     return T;
  72. }
  73.  
  74. bool check(ii cur){
  75.     if (CCW(st[2] - st[1], cur - st[1]) > 0) return 0;
  76.     if (CCW(st[h - 1] - st[1], cur - st[1]) < 0) return 0;
  77.  
  78.     auto L = [&]() -> int{
  79.         int lo = 2, hi = h - 1;
  80.         while (lo < hi){
  81.             int mid = (lo + hi + 1) >> 1;
  82.             int T = CCW(st[mid] - st[1], cur - st[1]);
  83.             if (T > 0) hi = mid - 1;
  84.             else lo = mid;
  85.         }
  86.         return lo;
  87.     }();
  88.  
  89.     auto R = [&]() -> int{
  90.         int lo = 2, hi = h - 1;
  91.         while (lo < hi){
  92.             int mid = (lo + hi) >> 1;
  93.             int T = CCW(st[mid] - st[1], cur - st[1]);
  94.             if (T > 0) hi = mid;
  95.             else lo = mid + 1;
  96.         }
  97.         return lo;
  98.     }();
  99.     if (CCW(st[L] - st[R], cur - st[R]) < 0) return 0;
  100.     if (L == R){
  101.         if (cur.X > st[L].X) return 0;
  102.         if ((st[1].Y <= st[L].Y && st[L].Y <= cur.Y)
  103.             || (st[1].Y >= st[L].Y && st[L].Y >= cur.Y)) return 0;
  104.         if ((st[L].Y <= st[1].Y && st[1].Y <= cur.Y)
  105.             || (st[L].Y >= st[1].Y && st[1].Y >= cur.Y)) return 0;
  106.     }
  107.     return 1;
  108. }
  109.  
  110. int Solve(){
  111.     h = 0;
  112.     sort(a + 1, a + 1 + n);
  113.     for (int i = 1; i <= n; ++i){
  114.         while (h > 1 && CCW(st[h] - st[h - 1], a[i] - st[h - 1]) >= 0) h--;
  115.         st[++h] = a[i];
  116.     }
  117.     int sz = h;
  118.     for (int i = n - 1; i >= 1; --i){
  119.         while (h > sz && CCW(st[h] - st[h - 1], a[i] - st[h - 1]) >= 0) h--;
  120.         st[++h] = a[i];
  121.     }
  122.  
  123.     /*for (int i = 1; i <= h; ++i){
  124.         cout << st[i].X << ' ' << st[i].Y << endl;
  125.     }
  126.  
  127.     cout << endl;
  128.  
  129.     return 0;*/
  130.  
  131.     int res = 0;
  132.  
  133.     for (int i = 1; i <= n; ++i){
  134.         if (check(b[i])) ++res;
  135.     }
  136.  
  137.     return res;
  138. }
  139.  
  140. signed main(){
  141.     init();
  142.     cout << Solve() << ' ';
  143.     swap(a,b);
  144.     cout << Solve();
  145.     return 0;
  146. }
RAW Paste Data