fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct rectangle {
  8.     int xmin, ymin, xmax, ymax;
  9. };
  10.  
  11. bool in(rectangle a, int x, int y) {
  12.     return x >= a.xmin && x <= a.xmax && y >= a.ymin && y <= a.ymax;
  13. }
  14.  
  15. bool sort_cmp(rectangle a, rectangle b) {
  16.     if (a.xmin != b.xmin) return a.xmin < b.xmin;
  17.     else return a.ymin < b.ymin;
  18. }
  19.  
  20. int bs(vector<rectangle> a, int x, int y) {
  21.     if (a.empty()) return -1;
  22.  
  23.     int l = 0, r = (int) a.size();
  24.     int result = -1;
  25.  
  26.     while (l <= r) {
  27.         int mid = (l + r) / 2;
  28.         if (x < a[mid].xmin || y < a[mid].ymin) {
  29.             r = mid - 1;
  30.         } else if (x > a[mid].xmax || y > a[mid].ymax) {
  31.             l = mid + 1;
  32.         } else {
  33.             result = mid;
  34.             r = mid - 1;
  35.         }
  36.     }
  37.     return result;
  38. }
  39.  
  40. int main() {
  41.  
  42.     int n, m, x, y;
  43.  
  44.     cin >> n >> m;
  45.  
  46.     vector<rectangle> a(n);
  47.  
  48.     for (int i = 0; i < n; i++) {
  49.         cin >> a[i].xmin >> a[i].xmax >> a[i].ymin >> a[i].ymax;
  50.     }
  51.  
  52.     sort(a.begin(), a.end(), sort_cmp);
  53.  
  54.     for (int i = 0; i < m; i++) {
  55.         cin >> x >> y;
  56.  
  57.         vector<rectangle> aux;
  58.  
  59.         int j = bs(a, x, y);
  60.  
  61.         if (j != -1) {
  62.             while (j < a.size()) {
  63.                 if (in(a[j], x, y)) {
  64.                     aux.push_back(a[j++]);
  65.                 } else break;
  66.             }
  67.         }
  68.  
  69.         cout << aux.size() << " ";
  70.  
  71.         a = aux;
  72.     }
  73.  
  74. }
  75.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wV91vD
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!