Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- typedef double db;
- typedef pair <int, int> pii;
- typedef pair <db, int> pdi;
- typedef pair <int, string> pis;
- typedef long long ll;
- const double EPS = 1e-9;
- const double INC_EPS = 1e-7;
- const int N = 1e5 + 5;
- struct coord
- {
- int c, ind;
- db x;
- coord(db _x = 0, int _c = 0, int _ind = 0)
- {
- x = _x;
- c = _c;
- ind = _ind;
- }
- bool operator < (coord t) const
- {
- return x < t.x || fabs(x - t.x) < EPS && c < t.c;
- }
- };
- int s[3 * N], size;
- void inc(int v, int value)
- {
- while (v <= size)
- {
- s[v] += value;
- v = v | (v + 1);
- }
- }
- int summ(int v)
- {
- int ret = 0;
- while (v >= 0)
- {
- ret += s[v];
- v = (v & (v + 1)) - 1;
- }
- return ret;
- }
- int get(int l, int r)
- {
- return summ(r) - summ(l - 1);
- }
- int n, m, x[N], y[N], f[3 * N];
- vector <pdi> sy;
- vector <coord> a;
- //horizontal h;
- int main()
- {
- cin >> n;
- for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
- x[n] = x[0];
- y[n] = y[0];
- for (int i = 0; i < n; i++)
- if (y[i] == y[i + 1])
- {
- sy.pb(mp(y[i], i));
- a.pb(coord(min(x[i], x[i + 1]), 0, i));
- a.pb(coord(max(x[i], x[i + 1]), 2, i));
- }
- cin >> m;
- db manx, many;
- for (int i = 0; i < m; i++)
- {
- cin >> manx >> many;
- //manx += INC_EPS;
- sy.pb(mp(many, i + n));
- a.pb(coord(manx, 1, i + n));
- }
- sort(sy.begin(), sy.end());
- sort(a.begin(), a.end());
- size = sy.size();
- int ans = 0;
- for (int i = 0; i < sy.size(); i++) f[sy[i].second] = i;
- //cout << a.size() << endl;
- for (int i = 0; i < a.size(); i++)
- {
- //cout << "ind = " << a[i].ind << " " << a[i].c << endl;
- if (!a[i].c) inc(f[a[i].ind], 1);
- else if (a[i].c == 2) inc(f[a[i].ind], -1);
- else
- {
- int z = get(f[a[i].ind], size);
- ans += z&1;
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement