Submission #697384

#	Time	Username	Problem	Language	Result	Execution time	Memory
697384		elkernos	Roads (CEOI20_roads)	C++17	100 / 100	189 ms	20040 KiB

roads

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct P {
    int x, y;
    bool operator<(const P &he) const { return make_pair(x, y) < make_pair(he.x, he.y); }
    void read() { cin >> x >> y; }
};

int sweep_x;
struct S {
    P one, two;
    int id;
    double sweep_y() const
    {
        if (one.x == two.x) return one.y;
        return one.y + (double)(two.y - one.y) * (sweep_x - one.x) / (two.x - one.x);
    }
    bool operator<(const S &he) const { return sweep_y() < he.sweep_y(); }
};

struct E {
    S seg;
    bool is_new;
    P point() const { return is_new ? seg.one : seg.two; }
    bool operator<(const E &he) const { return point() < he.point(); }
};  

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    int cnt = 1;
    vector<E> events;
    for (int i = 1; i <= n; i++) {
        P a, b;
        a.read(), b.read();
        if (!(a < b)) swap(a, b);
        events.push_back(E{S{a, b, cnt}, 1});
        events.push_back(E{S{a, b, cnt}, 0});
        cnt++;
    }
    const int oo = 1e9 + 7;
    set<S> on_line;
    for (auto y : {-oo, +oo}) {
        on_line.insert(S{{-oo, y}, {+oo, y}, cnt});
        cnt++;
    }
    vector<P> lower(cnt, {-oo, -oo}), upper(cnt, {-oo, -oo});
    sort(events.begin(), events.end());
    for (auto &e : events) {
        sweep_x = e.point().x;
        if (e.is_new) {
            auto it = on_line.upper_bound(e.seg);
            P maybe = lower[it->id];
            it--;
            maybe = max(maybe, upper[it->id]);
            if (maybe.x != -oo) cout << maybe.x << " " << maybe.y << " " << e.point().x << " " << e.point().y << '\n';
        }
        if (e.is_new) {
            auto it = on_line.insert(e.seg).first;
            lower[it->id] = upper[it->id] = e.point();
        }
        else on_line.erase(e.seg);
        auto it = on_line.upper_bound(e.seg);
        lower[it->id] = e.point();
        it--;
        upper[it->id] = e.point();
    }
}

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