• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.

Top