oj.uz

Submission #998759

# Submission time Handle Problem Language Result Execution time Memory
998759 2024-06-14T16:21:03 Z Trustfulcomic Roads (CEOI20_roads) C++14
0 / 100
 100 ms 4392 KB 
#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});

    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--;
            usecky.erase(it);
        } 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++;
            }
            usecky.insert(points[i]);
        }
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Failed 98 ms 4328 KB Condition failed: "iB != P2I.end()"
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Failed 100 ms 4392 KB Condition failed: "iB != P2I.end()"
3 Halted 0 ms 0 KB -