Submission #1111839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111839		doducanh	Roads (CEOI20_roads)	C++14	100 / 100	138 ms	13248 KiB

roads

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int inf=1e7;
const int maxn=1e5+7;
int x;
struct segment
{
    int x1,y1,x2,y2,rx,ry;
    int id;
    double get_y() const{
        return (x1==x2? y1 : y1 + (double)(y2 - y1) / (x2 - x1) * (x - x1));
    }
    bool operator<(segment const &s) const { return get_y() < s.get_y(); }
}a[maxn];
struct event
{
    int x,y,type,id;
};
bool cmp(const event &a,const event &b)
{
    return (a.x<b.x||(a.x==b.x&&a.y<b.y));
}
int n;
vector<event>events;
void sol(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
        if (a[i].x2 < a[i].x1 || (a[i].x1 == a[i].x2 && a[i].y2 < a[i].y1))
            swap(a[i].x1, a[i].x2), swap(a[i].y1, a[i].y2);
        a[i].id=i;
        events.push_back({a[i].x1,a[i].y1,0,i});
        events.push_back({a[i].x2,a[i].y2,1,i});
    }
    sort(events.begin(),events.end(),cmp);
    a[n].x1=-inf,a[n].x2=inf,a[n].y1=-inf,a[n].y2=-inf;
    a[n].rx=-inf,a[n].ry=-inf;
    a[n].id=n;
    auto compare_segment = [](auto const &i, auto const &j)
    { return a[i] < a[j]; };
    set<int, decltype(compare_segment)> s(compare_segment);
    s.insert(n);
    for(event tmp:events){
        x=tmp.x;
        if(tmp.type==0){
            auto it=s.lower_bound(tmp.id);
            it--;
            if(a[*it].rx!=-inf){
                cout<<a[*it].rx<<" "<<a[*it].ry<<" "<<a[tmp.id].x1<<" "<<a[tmp.id].y1<<"\n";
            }
            a[*it].rx=a[tmp.id].x1;
            a[*it].ry=a[tmp.id].y1;
            it=s.insert(tmp.id).fi;
            a[*it].rx=a[tmp.id].x1;
            a[*it].ry=a[tmp.id].y1;
        }
        else{
            auto it=s.find(tmp.id);
            it=--s.erase(it);
            a[*it].rx=a[tmp.id].x2;
            a[*it].ry=a[tmp.id].y2;
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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