Advertisement
Guest User

Untitled

a guest
Jun 26th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.51 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Point
  8. {
  9.     int x, y;
  10.     Point(int x = 0, int y = 0) : x(x), y(y){}
  11. };
  12.  
  13. bool operator == (const Point & a, const Point & b)
  14. {
  15.     return a.x == b.x && a.y == b.y;
  16. }
  17.  
  18. int INF = 1000*1000*1000;
  19. Point INF_P(-INF, INF);
  20.  
  21. bool cmpX(const Point & a, const Point & b)
  22. {
  23.     return a.x < b.x || (a.x == b.x && a.y < b.y);
  24. }
  25. bool cmpY(const Point & a, const Point & b)
  26. {
  27.     return a.y < b.y || (a.y == b.y && a.x < b.x);
  28. }
  29.  
  30. bool inside(int pos, const Point & a)
  31. {
  32.     return a.x <= pos && pos <= a.y;
  33. }
  34. bool fullInside(const Point & a, const Point & b)
  35. {
  36.     return a.x >= b.x && a.y <= b.y;
  37. }
  38.  
  39. bool intersected(const Point & a, const Point & b)
  40. {
  41.     return max(a.x, b.x) <= min(a.y, b.y);
  42. }
  43.  
  44. struct Map
  45. {
  46.     int n;
  47.     vector<Point> p;
  48.  
  49.     Map(int n = 0) : n(n), p(0){}
  50.  
  51.     void build()
  52.     {
  53.         _build(0, 0, n);
  54.     }
  55.  
  56.     void _build(bool byY, int l, int r)
  57.     {
  58.         if(l+1 >= r)
  59.             return;
  60.         int mid = (l + r)/2;
  61.  
  62.         if(byY)
  63.         {
  64.             nth_element(p.begin() + l, p.begin() + mid, p.begin() + r, cmpY);
  65.         }
  66.         else
  67.         {
  68.             nth_element(p.begin() + l, p.begin() + mid, p.begin() + r, cmpX);
  69.         }
  70.         _build(!byY, l, mid);
  71.         _build(!byY, mid + 1, r);
  72.     }
  73.  
  74.     int getCount(Point X, Point Y)
  75.     {
  76.         return _getCount(0, X, Y, 0, n);
  77.     }
  78.     int _getCount(bool byY, Point X, Point Y, int l, int r)
  79.     {
  80.         if(l >= r)
  81.             return 0;
  82.         if(l + 1 == r)
  83.             return inside(p[l].x, X) && inside(p[l].y, Y);
  84.  
  85.         if(X == INF_P && Y == INF_P)
  86.             return r - l;
  87.  
  88.         int mid = (l + r)/2;
  89.         int cnt = inside(p[mid].x, X) && inside(p[mid].y, Y);
  90.  
  91.         if(byY)
  92.         {
  93.             if(p[mid].y > Y.y)
  94.             {
  95.                 cnt += _getCount(!byY, X, Y, l, mid);
  96.             }
  97.             else
  98.             if(p[mid].y < Y.x)
  99.             {
  100.                 cnt += _getCount(!byY, X, Y, mid+1, r);
  101.             }
  102.             else
  103.             {
  104.                 cnt += _getCount(!byY, X, Point(Y.x, INF), l, mid);
  105.                 cnt += _getCount(!byY, X, Point(-INF, Y.y), mid+1, r);
  106.             }
  107.  
  108.         }
  109.         else
  110.         {
  111.             if(p[mid].x > X.y)
  112.             {
  113.                 cnt += _getCount(!byY, X, Y, l, mid);
  114.             }
  115.             else
  116.             if(p[mid].x < X.x)
  117.             {
  118.                 cnt += _getCount(!byY, X, Y, mid+1, r);
  119.             }
  120.             else
  121.             {
  122.                 cnt += _getCount(!byY, Point(X.x, INF), Y, l, mid);
  123.                 cnt += _getCount(!byY, Point(-INF, X.y), Y, mid+1, r);
  124.             }
  125.  
  126.         }
  127.  
  128.         return cnt;
  129.     }
  130. };
  131.  
  132. istream & operator >> (istream & in, Point & toRead)
  133. {
  134.     in >> toRead.x >> toRead.y;
  135.     return in;
  136. }
  137.  
  138. istream & operator >> (istream & in, Map & toRead)
  139. {
  140.     in >> toRead.n;
  141.     toRead.p.resize(toRead.n);
  142.  
  143.     for(int i = 0; i<toRead.n; i++)
  144.         in >> toRead.p[i];
  145.  
  146.     toRead.build();
  147.  
  148.     return in;
  149. }
  150.  
  151.  
  152. int main()
  153. {
  154.     ios::sync_with_stdio(false);
  155.     cin.tie(0);
  156.  
  157.     Map M;
  158.     cin >> M;
  159.  
  160.     int q;
  161.     cin >> q;
  162.  
  163.     while(q--)
  164.     {
  165.         int x1, x2, y1, y2;
  166.         cin >> x1 >> x2 >> y1 >> y2;
  167.         if(x1 > x2)
  168.             swap(x1, x2);
  169.         if(y1 > y2)
  170.             swap(y1, y2);
  171.  
  172.         cout << M.getCount(Point(x1, x2), Point(y1, y2)) << '\n';
  173.     }
  174.  
  175.  
  176.  
  177.     return 0;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement