Submission #345999

#	Time	Username	Problem	Language	Result	Execution time	Memory
345999		doowey	Roads (CEOI20_roads)	C++14	100 / 100	371 ms	29084 KiB

roads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
const ld inf = 1e9;
ld C;

struct segm{
    pdd A;
    pdd B;
    int id;
    bool operator< (const segm &t) const {
        ld fa;
        if(A.fi == B.fi){
            fa = A.se;
        }
        else{
            fa = (B.se-A.se)/(B.fi-A.fi) * (C - A.fi) + A.se;
        }
        ld fb;
        if(t.A.fi == t.B.fi){
            fb = t.A.se;
        }
        else{
            fb = (t.B.se-t.A.se)/(t.B.fi-t.A.fi) * (C-t.A.fi) + t.A.se;
        }
        return fa < fb;
    }
    bool operator== (segm &t) const {
        return (id == t.id);
    }
};

pdd ai[N], bi[N];
pdd rig[N];
bool act[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<pair<pdd,int>> eve;
    for(int i = 0 ; i < n; i ++) {
        cin >> ai[i].fi >> ai[i].se >> bi[i].fi >> bi[i].se;
        if(ai[i] > bi[i]) swap(ai[i], bi[i]);
        eve.push_back(mp(ai[i],i));
        eve.push_back(mp(bi[i],i));
    }
    set<segm> sq;
    C = -inf;
    sq.insert({mp(-inf,inf),mp(inf,inf),n});
    rig[n]=mp(-inf,-inf);
    sort(eve.begin(), eve.end());
    int nid;
    int cr = 0;
    for(auto ii : eve){
        C = ii.fi.fi;
        if(!act[ii.se]){
            auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
            nid = it->id;

            if(rig[nid] != mp(-inf,-inf)){
                cout << (int)rig[nid].fi << " " << (int)rig[nid].se << " " << (int)ai[ii.se].fi << " " << (int)ai[ii.se].se << "\n";
            }

            rig[ii.se] = ii.fi;
            rig[nid] = ii.fi;
            act[ii.se]=true;
            sq.insert({ai[ii.se],bi[ii.se],ii.se});
        }
        else{
            sq.erase({ai[ii.se],bi[ii.se],ii.se});
            auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
            nid = it->id;
            rig[nid]=ii.fi;
        }
    }
    return 0;
}

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:66:9: warning: unused variable 'cr' [-Wunused-variable]
   66 |     int cr = 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