API tools faq
paste
Advertisement
tepyotin2

Hillwalk

tepyotin2
Jun 26th, 2025
213
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. ll cur_x;
  8.  
  9. struct Segment{
  10.     //Use struct to get segment and get each coordinate values for use later on
  11.     //Calculate y vals at each point from x1, x1+1, x1+2... x2
  12.     ll x1, y1, x2, y2, idx;
  13.     double coordinate() const{
  14.         if(x1 == x2) return y1;
  15.         //calculation comes from the position of the x coordinate and then comparing
  16.         //where the y coordinate is of each line underneath the line is at the x-point and using
  17.         //that to sort the values in the set
  18.         return y1+1.0*(y2-y1)*(cur_x-x1)/(x2-x1);
  19.     }
  20.     bool operator<(const Segment &a) const{
  21.         return coordinate() < a.coordinate();
  22.     }
  23.     bool operator==(const Segment &a) const{
  24.         return idx==a.idx;
  25.     }
  26. };
  27.  
  28. struct Event{
  29.     ll x, y, idx;
  30.     bool operator<(const Event &a) const{
  31.         if(x==a.x){
  32.             return y<a.y;
  33.         }
  34.         return x<a.x;
  35.     }
  36. };
  37.  
  38. int n;
  39. //int ans = 1;
  40.  
  41. int main(){
  42.     freopen("hillwalk.in", "r", stdin);
  43.     freopen("hillwalk.out", "w", stdout);
  44.    
  45.     cin >> n;
  46.     vector<Segment> hill(n);
  47.     vector<Event> event;
  48.     for(int i=0; i<n; i++){
  49.         ll x1, y1, x2, y2;
  50.         cin >> x1 >> y1 >> x2 >> y2;
  51.         hill[i] = {x1, y1, x2, y2, i};
  52.         event.push_back({x1, y1, i});
  53.         event.push_back({x2, y2, i});
  54.     }
  55.     sort(event.begin(), event.end());
  56.     set<Segment> s;
  57.     vector<bool> active(n, false);
  58.     int cur = 0;
  59.     auto it = s.begin();
  60.     int ans = 1;
  61.     for(Event e: event){
  62.         cur_x = e.x;
  63.         //if index is not active then that means it is the left point of the segment
  64.         //but if the index is already active then would need to make it not active anymore
  65.         if(!active[e.idx]){
  66.             s.insert(hill[e.idx]);
  67.             active[e.idx] = true;
  68.         }else{
  69.             if(cur == e.idx){
  70.                 //since at the end point of the segment already, have to check if the index is the one bessie
  71.                 //is currently on and is about to continue walking on if not then the hill doesn't really matter
  72.                 //just still need to make the hill inactive which is on line 84-85
  73.                 it = s.find(hill[e.idx]);
  74.                 if(it!=s.begin()){
  75.                     it--;
  76.                     ans++;
  77.                     //set.erase(it);
  78.                     cur = (*it).idx;
  79.                     //cout << (*it).idx << '\n';
  80.                 }else{
  81.                     break;
  82.                 }
  83.             }
  84.             s.erase(hill[e.idx]);
  85.             active[e.idx] = false;
  86.         }
  87.     }
  88.     cout << ans << '\n';
  89.    
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!