Submission #998765

#	Time	Username	Problem	Language	Result	Execution time	Memory
998765		Trustfulcomic	Roads (CEOI20_roads)	C++14	100 / 100	277 ms	12116 KiB

roads

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

typedef pair<int,int> pii;
#define x first
#define y second

struct Usecka{
    pii a,b;
    int idx;
};

bool stejny(Usecka a, Usecka b){
    if ((a.a.x == b.a.x && a.a.y == b.a.y && a.b.x == b.b.x && a.b.y == b.b.y) || (a.a.x == b.b.x && a.a.y == b.b.y && a.b.x == b.a.x && a.b.y == b.a.y)){
        return true;
    }
    return false;
}

bool comp(const Usecka& l, const Usecka& r){
    if ((l.a.x == r.a.x && l.a.y == r.a.y && l.b.x == r.b.x && l.b.y == r.b.y) || (l.a.x == r.b.x && l.a.y == r.b.y && l.b.x == r.a.x && l.b.y == r.a.y)){
        return false;
    }
    bool prohozeny = false;
    Usecka u;
    pii b;
    if (min(l.a.x,l.b.x) >= min(r.a.x,r.b.x) && min(l.a.x,l.b.x) <= max(r.a.x,r.b.x)){
        b = min(l.a, l.b);
        u = r;
    } else {
        b = min(r.a, r.b);
        u = l;
        prohozeny = true;
    }

    if (u.a.x == u.b.x || b.x == u.a.x){
        return prohozeny^(u.a.y>b.y);
    } else {
        long double ynko = u.a.y + ((long double)(u.b.y-u.a.y)*(b.x-u.a.x))/((long double)(u.b.x-u.a.x));
        return prohozeny^(ynko>b.y);
    }

}

int main(){
    int n; cin >> n;
    vector<Usecka> points(2*n);
    for (int i = 0; i<n; i++){
        int a,b,c,d; cin >> a >> b >> c >> d;
        points[2*i] = {{a,b},{c,d},i};
        points[2*i+1] = {{c,d},{a,b},i};
    }

    sort(points.begin(), points.end(), [](const Usecka& l, const Usecka &r){
        return (l.a.x < r.a.x) || (l.a.x == r.a.x && l.a.y < r.a.y);
    });

    vector<pii> nad(n, {INT_MAX,INT_MAX});
    vector<pii> pod(n, {INT_MAX,INT_MAX});

    pii last_deleted = {INT_MAX,INT_MAX};

    set<Usecka, decltype(&comp)> usecky(&comp);
    usecky.insert(points[0]);
    nad[points[0].idx] = points[0].a;
    pod[points[0].idx] = points[0].a;
    for (int i = 1; i<2*n; i++){
        auto it = usecky.lower_bound(points[i]);
        if (it != usecky.end() && stejny(*it, points[i])){
            if (it != usecky.begin()){
                it--;
                nad[it->idx] = points[i].a;
                it++;
            }
            it++;
            if (it != usecky.end()){
                pod[it->idx] = points[i].a;
            }
            it--;
            last_deleted = points[i].a;
            usecky.erase(it);
        } else {
            if (usecky.size() == 0){
                cout << points[i].a.x << " " << points[i].a.y << " " << last_deleted.x << " " << last_deleted.y << endl;
            } else {
                if (it != usecky.end()){
                    cout << points[i].a.x << " " << points[i].a.y << " " << pod[it->idx].x << " " << pod[it->idx].y << endl;
                } else {
                    it--;
                    cout << points[i].a.x << " " << points[i].a.y << " " << nad[it->idx].x << " " << nad[it->idx].y << endl;
                    it++;
                }
            }

            if (it != usecky.end()){
                pod[it->idx] = points[i].a;
            }
            if (it != usecky.begin()){
                it--;
                nad[it->idx] = points[i].a;
                it++;
            }
            nad[points[i].idx]=points[i].a;
            pod[points[i].idx]=points[i].a;
            usecky.insert(points[i]);
        }
    }
}

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