Submission #701626

#	Time	Username	Problem	Language	Result	Execution time	Memory
701626		Cyanmond	Roads (CEOI20_roads)	C++17	100 / 100	586 ms	47556 KiB

roads

#include <bits/stdc++.h>

using i64 = long long;
struct Point {
    i64 x;
    i64 y;
};

constexpr double eps = 1e-9;
struct Segment {
    Point a;
    Point b;

    double eval(i64 x) {
        assert(a.x <= b.x);
        if (a.x == b.x) {
            return a.y;
        } else {
            double ac = a.y * (b.x - x);
            double bc = b.y * (x - a.x);
            return (ac + bc) / (double)(b.x - a.x);
        }
    }
};

constexpr i64 maxC = 20000000;

int main() {
    auto compSegment = [](Segment a, Segment b) -> bool {
        // not cross
        bool isSwapped = false;
        if (a.a.x < b.a.x) {
            std::swap(a, b);
            isSwapped = true;
        }
        i64 s = a.a.y;
        const auto t = b.eval(a.a.x);
        bool u = s - t < eps;
        bool eq = std::abs(s - t) < eps;
        if (eq) {
            return false;
        }
        return u xor isSwapped;
    };
    auto compPoint = [](Point a, Point b) {
        // tokuni iminasi
        return a.x * maxC + a.y < b.x * maxC + b.y;
    };

    int N;
    std::cin >> N;
    std::vector<Segment> segments(N);
    for (auto &[as, bs] : segments) {
        auto &[ax, ay] = as;
        auto &[bx, by] = bs;
        std::cin >> ax >> ay >> bx >> by;
    }
    // std::map<i64, std::vector<int>> addList, eraseList;
    std::map<i64, std::vector<std::pair<int, bool>>> eventList;
    for (int i = 0; i < N; ++i) {
        auto &[as, bs] = segments[i];
        if (as.x > bs.x) {
            std::swap(as, bs);
        }
        if (as.x == bs.x) {
            assert(as.y != bs.y);
            if (as.y > bs.y) {
                std::swap(as, bs);
            }
        }
        eventList[as.x].push_back({i, true});
        eventList[bs.x].push_back({i, false});
    }
    std::map<Point, std::pair<int, bool>, decltype(compPoint)> indexList(compPoint);
    for (int i = 0; i < N; ++i) {
        indexList[segments[i].a] = {i, true};
        indexList[segments[i].b] = {i, false};
    }
    
    std::set<Segment, decltype(compSegment)> segmentSet(compSegment);
    std::vector<Point> safePoint(N);
    std::vector<std::pair<Point, Point>> answer;
    Point safeMi;
    bool isFirst = true;
    for (auto &[xVal, vec] : eventList) {
        std::sort(vec.begin(), vec.end(), [&](auto &a, auto &b) {
            const auto c = a.second ? segments[a.first].a : segments[a.first].b;
            const auto d = b.second ? segments[b.first].a : segments[b.first].b;
            return c.y < d.y;
        });
        for (const auto &[i, type] : vec) {
            if (type) {
                auto itr = segmentSet.insert(segments[i]).first;
                if (itr == segmentSet.begin()) {
                    if (isFirst) {
                        safeMi = segments[i].a;
                        isFirst = false;
                    } else {
                        answer.push_back({segments[i].a, safeMi});
                        safeMi = segments[i].a;
                    }
                    safePoint[i] = segments[i].a;
                    if (segments[i].a.x == segments[i].b.x) {
                        safePoint[i] = segments[i].b;
                        // ok ?
                    }
                    continue;
                }
                --itr;
                answer.push_back({segments[i].a, safePoint[indexList[itr->a].first]});
                safePoint[indexList[itr->a].first] = segments[i].a;
                safePoint[i] = segments[i].a;
                if (segments[i].a.x == segments[i].b.x) {
                    safePoint[i] = segments[i].b;
                    // ok ?
                }
            } else {
                auto itr = segmentSet.find(segments[i]);
                itr = segmentSet.erase(itr);
                if (itr == segmentSet.begin()) {
                    safeMi = segments[i].b;
                    continue;
                }
                --itr;
                safePoint[indexList[itr->a].first] = segments[i].b;
            }
        }
    }

    assert(answer.size() == N - 1);
    for (const auto &[ap, bp] : answer) {
        std::cout << ap.x << ' ' << ap.y << ' ' << bp.x << ' ' << bp.y << std::endl;
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from roads.cpp:1:
roads.cpp: In function 'int main()':
roads.cpp:130:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<Point, Point> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |     assert(answer.size() == N - 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~

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