Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define double long double
- #define Task "NEWCARO"
- #define READFILE freopen(Task".inp", "r", stdin)
- #define WRITEFILE freopen(Task".out", "w", stdout)
- #define double long double
- #define oo 0x3f3f3f3f3f
- #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define mp make_pair
- #define pb push_back
- #define X first
- #define Y second
- #define watch(x) cout << (#x) << " = " << x << endl
- #define debug(x) cout << (#x) << " = " << x << endl
- #define all(x) x.begin(), x.end()
- #define sz(x) x.size()
- #define endl '\n'
- #define max3(a,b,c) max(max(a, b), c)
- #define max4(a,b,c,d) max(max(a, b), max(c, d))
- #define min4(a,b,c,d) min(min(a, b), min(c, d))
- #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
- #define ever (;true;)
- #define maxn 505
- #define PI 3.14159265
- using namespace std;
- typedef pair < int, int > ii;
- typedef pair < int, ii > iii;
- typedef pair < ii, ii > iiii;
- typedef vector < int > vi;
- typedef vector < ii > vii;
- typedef vector < vi > vvi;
- typedef vector < iii > viii;
- typedef vector < vii > vvii;
- typedef vector < iiii > viiii;
- typedef vector < vvi > vvvi;
- const int N = 5e4 + 5;
- int n;
- ii a[N], b[N];
- ii st[N];
- int h = 0;
- void init(){
- FAST;
- #ifndef ONLINE_JUDGE
- READFILE;
- WRITEFILE;
- #endif // ONLINE_JUDGE
- cin >> n;
- for (int i = 1; i <= n; ++i){
- cin >> a[i].X >> a[i].Y;
- }
- for (int i = 1; i <= n; ++i){
- cin >> b[i].X >> b[i].Y;
- }
- }
- ii operator - (const ii &a, const ii &b){
- return ii(a.X - b.X, a.Y - b.Y);
- }
- int CCW(ii u, ii v){
- int T = u.X * v.Y - u.Y * v.X;
- if (T > 0) return 1;
- if (T < 0) return -1;
- return T;
- }
- bool check(ii cur){
- if (CCW(st[2] - st[1], cur - st[1]) > 0) return 0;
- if (CCW(st[h - 1] - st[1], cur - st[1]) < 0) return 0;
- auto L = [&]() -> int{
- int lo = 2, hi = h - 1;
- while (lo < hi){
- int mid = (lo + hi + 1) >> 1;
- int T = CCW(st[mid] - st[1], cur - st[1]);
- if (T > 0) hi = mid - 1;
- else lo = mid;
- }
- return lo;
- }();
- auto R = [&]() -> int{
- int lo = 2, hi = h - 1;
- while (lo < hi){
- int mid = (lo + hi) >> 1;
- int T = CCW(st[mid] - st[1], cur - st[1]);
- if (T > 0) hi = mid;
- else lo = mid + 1;
- }
- return lo;
- }();
- if (CCW(st[L] - st[R], cur - st[R]) < 0) return 0;
- if (L == R){
- if (cur.X > st[L].X) return 0;
- if ((st[1].Y <= st[L].Y && st[L].Y <= cur.Y)
- || (st[1].Y >= st[L].Y && st[L].Y >= cur.Y)) return 0;
- if ((st[L].Y <= st[1].Y && st[1].Y <= cur.Y)
- || (st[L].Y >= st[1].Y && st[1].Y >= cur.Y)) return 0;
- }
- return 1;
- }
- int Solve(){
- h = 0;
- sort(a + 1, a + 1 + n);
- for (int i = 1; i <= n; ++i){
- while (h > 1 && CCW(st[h] - st[h - 1], a[i] - st[h - 1]) >= 0) h--;
- st[++h] = a[i];
- }
- int sz = h;
- for (int i = n - 1; i >= 1; --i){
- while (h > sz && CCW(st[h] - st[h - 1], a[i] - st[h - 1]) >= 0) h--;
- st[++h] = a[i];
- }
- /*for (int i = 1; i <= h; ++i){
- cout << st[i].X << ' ' << st[i].Y << endl;
- }
- cout << endl;
- return 0;*/
- int res = 0;
- for (int i = 1; i <= n; ++i){
- if (check(b[i])) ++res;
- }
- return res;
- }
- signed main(){
- init();
- cout << Solve() << ' ';
- swap(a,b);
- cout << Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement