SHARE
TWEET

Sweep line easy

a guest Aug 13th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Author: Rennan Rocha
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define PB push_back
  8. #define MP make_pair
  9.  
  10. #define ll long long
  11.  
  12. using namespace std;
  13.  
  14. struct event {
  15.     int x, y, flag;
  16.  
  17.     bool operator<(const event &b) const{
  18.         return x < b.x;
  19.     }
  20. };
  21.  
  22. int main() {
  23.     int n;
  24.     cin >> n;
  25.  
  26.     vector<event> events;
  27.  
  28.     for(int i = 0; i < n; i++) {
  29.         int x1, y1, x2, y2;
  30.         cin >> x1 >> y1 >> x2 >> y2;
  31.         event p1 = {x1,y1,1};
  32.         event p2 = {x2,y2,0};
  33.  
  34.         events.PB(p1);
  35.         events.PB(p2);
  36.     }
  37.  
  38.     sort(events.begin(), events.end());
  39.     multiset<int> alturas;
  40.     event last_event = {0,0,0};
  41.     ll ans = 0;
  42.     for(int i = 0; i < events.size(); i++) {
  43.         event ev = events[i];
  44.         if(ev.flag == 1) { //in
  45.             if(alturas.size() > 0)
  46.                 ans += (*(--alturas.end()) * (ev.x - last_event.x));
  47.             alturas.insert(ev.y);
  48.         }else { //out
  49.             if(alturas.size() > 0)
  50.                 ans += (*(--alturas.end()) * (ev.x - last_event.x));
  51.             alturas.erase(ev.y);
  52.         }
  53.         last_event = ev;
  54.     }
  55.     cout << ans << endl;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top