Submission #1204754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204754		byunjaewoo	Roads (CEOI20_roads)	C++20	15 / 100	40 ms	5820 KiB

roads

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;

const int N=100010, INF=1e7;
int n;
struct line {
    int k;
    array<int, 2> s, e;
    ld gety(int x) const {
        if(s[0]==e[0]) return s[1];
        return (ld)(s[1]*(e[0]-x)+e[1]*(x-s[0]))/(ld)(e[0]-s[0]);
    }
    bool operator<(const line &r) const {
        return (*this).gety(max(s[0], r.s[0]))<r.gety(max(s[0], r.s[0]));
    }
}a[N];
set<line> st;
array<int, 2> nxt[N];
vector<array<int, 4>> vec;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i].s[0]>>a[i].s[1]>>a[i].e[0]>>a[i].e[1], a[i].k=i;
        if(a[i].s>a[i].e) swap(a[i].s, a[i].e);
        vec.push_back({a[i].s[0], a[i].s[1], i, true});
        vec.push_back({a[i].e[0], a[i].e[1], i, false});
    }
    sort(vec.begin(), vec.end());
    st.insert({0, {-INF, -INF}, {INF, -INF}}), st.insert(a[vec[0][2]]);
    nxt[0]=nxt[vec[0][2]]=a[vec[0][2]].s;
    if(a[vec[0][2]].s[0]==a[vec[0][2]].e[0]) nxt[0]=nxt[vec[0][2]]=a[vec[0][2]].e;
    for(auto [x, y, k, f]:vec) {
        if(k==vec[0][2] && f) continue;
        if(f) {
            st.insert(a[k]);
            auto p=prev(st.find(a[k]));
            cout<<x<<" "<<y<<" "<<nxt[a[p->k].k][0]<<" "<<nxt[a[p->k].k][1]<<"\n";
            if(a[k].s[0]==a[k].e[0]) nxt[k]=a[k].e;
            else nxt[k]=a[k].s;
        }
        else {
            auto p=prev(st.find(a[k]));
            nxt[a[p->k].k]=a[k].e;
            st.erase(a[k]);
        }
    }
    return 0;
}

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