제출 #1290905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290905		loom	Roads (CEOI20_roads)	C++20	100 / 100	182 ms	50056 KiB

roads

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define inf (int)2e18
#define nl '\n'

int cx;

struct pt{
   int x, y;

   void in(){
      cin>>x>>y;
   }

   bool operator < (const pt &p) const {
      return pair(x, y) < pair(p.x, p.y);
   }
};

struct seg{
   pt l, r;

   ld gety() const {
      if(l.x == r.x) return l.y;
      return l.y + (ld) (cx - l.x) * (r.y - l.y) / (r.x - l.x);
   }

   bool operator < (const seg &s) const {
      return gety() < s.gety();
   }
};

struct endp{
   seg sg;
   int isl;

   pt get() const {
      return isl ? sg.l : sg.r;
   }

   bool operator < (const endp &e) const {
      return get() < e.get();
   }
};

void solve(){
   int n;
   cin>>n;

   vector<endp> v;
   for(int i = 0; i < n; i++){
      pt l, r;
      l.in();
      r.in();

      if(r < l) swap(l, r);
      v.push_back({{l, r}, 0});
      v.push_back({{l, r}, 1});
   }

   sort(v.begin(), v.end());
   seg low = {{-inf, -inf}, {inf, -inf}};
   set<seg> st;
   st.insert(low);
   map<seg, pt> up;
   up[low] = low.l;

   for(auto ep : v){
      seg sg = ep.sg;
      pt p = ep.get();
      cx = p.x;

      if(ep.isl){
         seg lsg = *--st.lower_bound(sg);
         pt q = up[lsg];
         if(q.y != -inf){
            cout<<p.x<<" "<<p.y<<" "<<q.x<<" "<<q.y<<nl;
         }

         up[lsg] = p;
         st.insert(sg);
         up[sg] = p;
      }
      else{
         st.erase(sg);
         up.erase(sg);
         seg lsg = *--st.lower_bound(sg);
         up[lsg] = p;
      }
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40