Submission #1326028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326028		_callmelucian	Roads (CEOI20_roads)	C++17	30 / 100	153 ms	21244 KiB

roads

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

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct Point {
    ll x, y;

    Point() : x(0), y(0) {}
    Point (ll x, ll y) : x(x), y(y) {}

    bool operator< (const Point &o) const { return (x == o.x ? y < o.y : x < o.x); }
    bool operator> (const Point &o) const { return (x == o.x ? y > o.y : x > o.x); }
    Point operator+ (const Point &o) const { return Point(x + o.x, y + o.y); }
    Point operator- (const Point &o) const { return Point(x - o.x, y - o.y); }

    friend ll dot (const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
    friend ll cross (const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
    
    friend bool turnLeft (const Point &a, const Point &b, const Point &c) { return cross(b - a, c - b) > 0; }
    friend bool turnRight (const Point &a, const Point &b, const Point &c) { return cross(b - a, c - b) < 0; }

    friend istream& operator>> (istream &inp, Point &p) { return inp >> p.x >> p.y, inp; }
    friend ostream& operator<< (ostream &oup, const Point &p) { return oup << "(" << p.x << ", " << p.y << ")", oup; }
};

struct Segment {
    Point a, b;
    mutable Point rm;

    Segment() {}
    Segment (Point _a, Point _b) : a(_a), b(_b), rm(_a) {
        if (a > b) swap(a, b), rm = a;
    }

    bool operator< (const Segment &o) const {
        if (a.x == b.x and o.a.x == o.b.x) return b < o.b;
        if (a.x <= o.a.x and o.a.x <= b.x) return turnLeft(a, b, o.a);
        if (a.x <= o.b.x and o.b.x <= b.x) return turnLeft(a, b, o.b);
        return turnRight(o.a, o.b, a);
    }

    bool operator< (const Point &o) const {
        return (a.x == b.x ? b < o : turnLeft(a, b, o));
    }
};

const int mn = 2e5 + 10;
const int oo = 1e9;

multiset<Segment, less<void>> lineSet;
vector<int> cmpSet;
vector<pair<int, bool>> events[mn];

int getX (int targ) { return lower_bound(all(cmpSet), targ) - cmpSet.begin(); }

auto getToLeft (const Point &p) {
    auto itr = lineSet.lower_bound(p);
    if (itr == lineSet.begin()) {
        cout << "You may quit CP 1\n";
        exit(0);
    }
    return prev(itr);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    // read points coordinate and prepare compressed coordinate set
    int n; cin >> n;
    vector<pair<Point, Point>> vec(n), ans;
    for (int i = 0; i < n; i++) {
        cin >> vec[i].first >> vec[i].second;
        cmpSet.push_back(vec[i].first.x);
        cmpSet.push_back(vec[i].second.x);
        if (vec[i].first > vec[i].second)
            swap(vec[i].first, vec[i].second);
    }
    sort(all(cmpSet)), filter(cmpSet);

    // prepare sweep line events
    for (int i = 0; i < n; i++) {
        Point openPoint, endPoint;
        tie(openPoint, endPoint) = vec[i];
        events[getX(openPoint.x)].emplace_back(i, true);
        events[getX(endPoint.x)].emplace_back(i, false);
    }
    for (int x = 0; x < cmpSet.size(); x++) {
        // sort(all(openEvent[x]), [&] (int i, int j) { return vec[i].first.y < vec[j].first.y; });
        // sort(all(closeEvent[x]), [&] (int i, int j) { return vec[i].second.y < vec[j].second.y; });
        sort(all(events[x]), [&] (pair<int, bool> i, pair<int, bool> j) {
            Point p1 = (i.second ? vec[i.first].first : vec[i.first].second);
            Point p2 = (j.second ? vec[j.first].first : vec[j.first].second);
            return p1 < p2;
        });
    }

    // perform sweep line
    lineSet.emplace(Point(-oo, -oo), Point(oo, -oo)); // an infintely low horizontal line
    for (int i = 0; i < cmpSet.size(); i++) {
        for (auto [sID, isOpen] : events[i]) {
            if (isOpen) {
                auto itr = getToLeft(vec[sID].first);
                ans.emplace_back(itr->rm, vec[sID].first);
                itr->rm = vec[sID].first;
                lineSet.emplace(vec[sID].first, vec[sID].second);
            }
            else {
                auto itr = lineSet.lower_bound(vec[sID].second);
                if (itr == lineSet.end()) {
                    cout << "You may quit CP 2\n";
                    exit(0);
                }
                itr = lineSet.erase(itr);
                if (itr == lineSet.begin()) {
                    cout << "You may quit CP 3\n";
                    exit(0);
                }
                itr = prev(itr), itr->rm = vec[sID].second;
            }
        }

        // cout << "=== UPDATE SET ===\n";
        // for (auto [a, b, c] : lineSet) cout << "[" << a << ", " << b << ", " << c << "] ";
        // cout << "\n\n";
    }

    // print result
    for (int i = 1; i < ans.size(); i++) {
        cout << ans[i].first.x << " " << ans[i].first.y << " ";
        cout << ans[i].second.x << " " << ans[i].second.y << "\n";
    }

    return 0;
}

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