Advertisement
Guest User

Untitled

a guest
Feb 2nd, 2012
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7. #define pb push_back
  8. #define mp make_pair
  9. typedef double db;
  10. typedef pair <int, int> pii;
  11. typedef pair <db, int> pdi;
  12. typedef pair <int, string> pis;
  13. typedef long long ll;
  14. const double EPS = 1e-9;
  15. const double INC_EPS = 1e-7;
  16. const int N = 1e5 + 5;
  17.  
  18. struct coord
  19. {
  20.   int c, ind;
  21.   db x;
  22.   coord(db _x = 0, int _c = 0, int _ind = 0)
  23.   {
  24.     x = _x;
  25.     c = _c;
  26.     ind = _ind;
  27.   }
  28.   bool operator < (coord t) const
  29.   {
  30.     return x < t.x || fabs(x - t.x) < EPS && c < t.c;
  31.   }
  32. };
  33. int s[3 * N], size;
  34. void inc(int v, int value)
  35. {
  36.   while (v <= size)
  37.   {
  38.     s[v] += value;
  39.     v = v | (v + 1);
  40.   }
  41. }
  42. int summ(int v)
  43. {
  44.   int ret = 0;
  45.   while (v >= 0)
  46.   {
  47.     ret += s[v];
  48.     v = (v & (v + 1)) - 1;
  49.   }
  50.   return ret;
  51. }
  52. int get(int l, int r)
  53. {
  54.   return summ(r) - summ(l - 1);
  55. }
  56.  
  57. int n, m, x[N], y[N], f[3 * N];
  58. vector <pdi> sy;
  59. vector <coord> a;
  60. //horizontal h;
  61. int main()
  62. {
  63.   cin >> n;
  64.   for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  65.   x[n] = x[0];
  66.   y[n] = y[0];
  67.   for (int i = 0; i < n; i++)
  68.     if (y[i] == y[i + 1])
  69.     {
  70.       sy.pb(mp(y[i], i));
  71.       a.pb(coord(min(x[i], x[i + 1]), 0, i));
  72.       a.pb(coord(max(x[i], x[i + 1]), 2, i));
  73.     }
  74.   cin >> m;
  75.   db manx, many;
  76.   for (int i = 0; i < m; i++)
  77.   {
  78.     cin >> manx >> many;
  79.     //manx += INC_EPS;
  80.     sy.pb(mp(many, i + n));
  81.     a.pb(coord(manx, 1, i + n));
  82.   }
  83.   sort(sy.begin(), sy.end());
  84.   sort(a.begin(), a.end());
  85.   size = sy.size();
  86.   int ans = 0;
  87.   for (int i = 0; i < sy.size(); i++) f[sy[i].second] = i;
  88.   //cout << a.size() << endl;
  89.   for (int i = 0; i < a.size(); i++)
  90.   {
  91.     //cout << "ind = " << a[i].ind << " " << a[i].c << endl;
  92.     if (!a[i].c) inc(f[a[i].ind], 1);
  93.     else if (a[i].c == 2) inc(f[a[i].ind], -1);
  94.     else
  95.     {
  96.       int z = get(f[a[i].ind], size);
  97.       ans += z&1;
  98.     }
  99.   }
  100.   cout << ans;
  101.   return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement