Submission #1185714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185714		Unforgettablepl	Roads (CEOI20_roads)	C++20	30 / 100	97 ms	11224 KiB

roads

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

int c = 0;

struct line{
    int x1,x2,y1,y2,id;
    line(int x1,int y1,int x2,int y2):x1(x1),y1(y1),x2(x2),y2(y2),id(++c){}
    long double operator()(int x) const{
        if(x==x2)return (ld)y2;
        if(x1==x2)return (ld)y2; // edge case
        return (ld)(y2-y1)*(ld)(x-x1)/(ld)(x2-x1) + (ld)y1;
    }
    pair<__int128,__int128> alter(int x)const{
        return {(y2-y1)*(x-x1) + y1*(x2-x1), x2-x1};
    }
    
    bool operator<(const line& other) const{
        int pt = max(x1,other.x1);
        if(x1==x2 or other.x1==other.x2)return this->operator()(pt) < other(pt);
        return alter(pt).first*other.alter(pt).second < alter(pt).second*other.alter(pt).first;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<tuple<int,int,int,int>> lines(N);
    map<int,vector<int>> removals;
    for(auto&[x1,y1,x2,y2]:lines){
        cin >> x1 >> y1 >> x2 >> y2;
        if(make_pair(x1,y1) > make_pair(x2,y2)){
            swap(x1,x2);
            swap(y1,y2);
        }
    }
    sort(lines.begin(),lines.end());
    map<pair<int,int>,pair<int,int>> opt; // [lidx,ridx] -> (y,x)
    set<line> limits;
    vector<line> answer;
    limits.emplace(-1e8,-1e8,1e8,-1e8);
    limits.emplace(-1e8,1e8,1e8,1e8);
    opt[{1,2}] = {-1e8,-1e8};
    auto findLimits = [&](int x,int y){
        int upper = limits.upper_bound(line(x,y,x,y))->id;
        int lower = (--limits.upper_bound(line(x,y,x,y)))->id;
        return make_pair(lower,upper);
    };
    for(auto&[x1,y1,x2,y2]:lines){
        // process removals
        while(removals.begin()!=removals.end() and removals.begin()->first<x1){
            for(int&i:removals.begin()->second){
                limits.erase(limits.lower_bound(line(removals.begin()->first,i,removals.begin()->first,i))); // figure out how to delete
                opt[findLimits(removals.begin()->first,i)]=max(opt[findLimits(removals.begin()->first,i)],{removals.begin()->first,i});
            }
            removals.erase(removals.begin());
        }
        for(int&i:removals[x1]){
            opt[findLimits(x1,i)]=max(opt[findLimits(x1,i)],{x1,i});
            opt[findLimits(x1,i-1)]=max(opt[findLimits(x1,i-1)],{x1,i});
        }
        // process actually
        auto lim = findLimits(x1,y1);
        if(x1==x2 and opt[{lim.first,lim.second}].second>y1){
            answer.emplace_back(x1,y2,opt[{lim.first,lim.second}].first,opt[{lim.first,lim.second}].second);
        } else answer.emplace_back(x1,y1,opt[{lim.first,lim.second}].first,opt[{lim.first,lim.second}].second);
        // add this to removals if not vertical
        auto t = findLimits(x1,y1);
        if(x1!=x2){
            removals[x2].emplace_back(y2);
            // add this to limitations
            limits.emplace(x1,y1,x2,y2);
            opt[{t.first,c}]={x1,y1};
            opt[{c,t.second}]={x1,y1};
        } else {
            opt[t]={x1,y2};
        }
    }
    for(line&x:answer){
        if(x.x2<-1e7)continue;
        cout << x.x1 << ' ' << x.y1 << ' ' << x.x2 << ' ' << x.y2 << '\n';
    }
}

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