8. Absurdistanské diaľnice vzorové riešenie

#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
#include <cstdio>
#include <set>

using namespace std;

#define FOR(i,n) for(int i = 0; i<(n); ++i)
bool dfs(int a, int vrstva, vector<vector<int>>& G, vector<int>& z_b_do_a, vector<int>& A, vector<int>& B) {
    if (A[a] != vrstva) return 0;
    A[a] = -1;
    for (int b : G[a]) if (B[b] == vrstva + 1) {
            B[b] = 0;
            if (z_b_do_a[b] == -1 || dfs(z_b_do_a[b], vrstva + 1, G, z_b_do_a, A, B))
                return z_b_do_a[b] = a, 1;
        }
    return 0;
}

int hopcroftKarp(vector<vector<int>>& G, vector<int>& btoa) {
    int res = 0;
    vector<int> A(G.size()), B(btoa.size()), terajsia_vrstva, dalsia_vrstva;
    while (true) {
        //polia A a B budu obsahovat vzdialenost po striedavych cestach z nesparovanych vrcholov v A
        fill(A.begin(), A.end(), 0);
        fill(B.begin(), B.end(), 0);
        /// Najdenie nesparovanych vrcholov v A
        terajsia_vrstva.clear();
        // -1 su sparovane vrcholy v A
        for (int a : btoa) if(a != -1) A[a] = -1;
        FOR(a, G.size()) if(A[a] == 0) terajsia_vrstva.push_back(a);
        //
        for (int vrstva = 1; true; vrstva++) {
            bool posledna = false;
            dalsia_vrstva.clear();
            for (int a : terajsia_vrstva) for (int b : G[a]) {
                    if (btoa[b] == -1) {
                        //nasli sme zlepsujucu cestu
                        B[b] = vrstva;
                        posledna = true;
                    }
                    else if (btoa[b] != a && !B[b]) {
                        //tento vrchol je uz sparovany a teda haladame alternujucu cestu cez jeho sparovanu hranu
                        B[b] = vrstva;
                        dalsia_vrstva.push_back(btoa[b]);
                    }
                }
            if (posledna) break;
            //nenasli sme zlepsujucu cestu ale nie je kam pokracovat teda mame maximalne parenie
            if (dalsia_vrstva.empty()) return res;

            for (int a : dalsia_vrstva) A[a] = vrstva;
            terajsia_vrstva.swap(dalsia_vrstva);
        }
        /// Use DFS to scan for augmenting paths.
        FOR(a, G.size())
            res += dfs(a, 0, G, btoa, A, B);
    }
}

//najde vrcholove pokrytie, vyuziva minimalne parenie
vector<int> vrcholove_pokrytie(vector<vector<int>>& g, int A, int B) {
    vector<int> z_b_do_a(B, -1);
    int res = hopcroftKarp(g, z_b_do_a);
    vector<bool> X(A, true), Y(B);

    //oznaci vrcholy, ktore su sparene, ako tie, ktore zatial nie su v X, vsetky ostatne su v X0
    for (int b : z_b_do_a) if (b != -1) X[b] = false;

    // kedze nam nezalezi na poradi vrcholov pocas vyhladavania (chceme iba najst vrcholy v X), tak mozeme namiesto fronty pouzit vector ako stack
    vector<int> q, C;
    // na zaciatku do stacku prehladavanych vrcholov pridame vrcholy z X_0
    for(int i=0; i<A; i++) if (X[i]) q.push_back(i);


    while (!q.empty()) {
        int a = q.back(); q.pop_back();
        // pridame vrchol a do X
        X[a] = true;
        for (int b : g[a]) if (!Y[b] && z_b_do_a[b] != -1) {
                // ak sme vrchol b doteraz nevideli a je spareny, tak ho pridame do Y
                // ak je spareny, tak sa uz nechceme vracat po hrane, v ktorej sme uz boli
                Y[b] = true;
                q.push_back(z_b_do_a[b]);
            }
    }
    // na zaver precislujeme vrcholy napravo a vratime vector vrcholov v najmensom vrcholovom pokryti
    for(int i = 0; i < A; i++) if (!X[i]) C.push_back(i);
    for(int i = 0; i < B; i++) if (Y[i]) C.push_back(A + i);
    return C;
}



long long getn() {
    long long x;
    scanf("%lld",&x);
    return x;
}
typedef tuple<int,int, bool> dialnicny_usek;
int main() {
    map<int, map<int, int>> YX;
    map<int, map<int, int>> XY;
    map<int, map<int, int>> krdole;
    map<int, map<int, int>> krdoprava;
    int n = getn();
    FOR(i,n) {
        int x=getn();
        int y=getn();
        YX[y][x]=i;
        XY[x][y]=i;
    }
    //zlava doprava


    vector<vector<dialnicny_usek> > nechcene_krizenia;
    map<dialnicny_usek, int> mapa_zvislych_usekov, mapa_vodorovnych_usekov;
    for (const auto &it1: YX)
    {
        int y = it1.first;
        for (const auto &it2: XY) {
            int x = it2.first;
            auto it = it2.second.lower_bound(y);
            auto it_pred_x = it1.second.lower_bound(x);
            if(it->first != y && it!=it2.second.begin() && it != it2.second.end()
            && it_pred_x->first != x && it_pred_x != it1.second.begin() && it_pred_x != it1.second.end())
            {
                //x y zvisly?
                auto it3= it1.second.lower_bound(x);
                nechcene_krizenia.push_back({{x, it->first, true}, {it3->first, y, false}});
                mapa_zvislych_usekov[{x, it->first, true}] = 0;
                mapa_vodorovnych_usekov[{it3->first, y, false}] = 0;
            }
        }
    }
    vector<dialnicny_usek> pole_zvislych_usekov;
    for (auto &usek : mapa_zvislych_usekov) {
        usek.second = pole_zvislych_usekov.size();
        pole_zvislych_usekov.push_back(usek.first);
    }

    vector<dialnicny_usek> pole_vodorovnych_usekov;
    for (auto &usek : mapa_vodorovnych_usekov) {
        usek.second = pole_vodorovnych_usekov.size();
        pole_vodorovnych_usekov.push_back(usek.first);
    }

    vector<vector<int> > nechcene_krizenia_graf(pole_zvislych_usekov.size());
    for (auto &krizenie : nechcene_krizenia) {
        nechcene_krizenia_graf[mapa_zvislych_usekov[krizenie[0]]].push_back(mapa_vodorovnych_usekov[krizenie[1]]);
    }

    vector<int> cov = vrcholove_pokrytie(
            nechcene_krizenia_graf,
            nechcene_krizenia_graf.size(),
            pole_vodorovnych_usekov.size());

    set<dialnicny_usek> nepostavime;
    for (int i : cov) {
        dialnicny_usek d;
        if (i < mapa_zvislych_usekov.size()) {
            d = pole_zvislych_usekov[i];
        } else {
            d = pole_vodorovnych_usekov[i - mapa_zvislych_usekov.size()];
        }
        nepostavime.insert(d);
    }

    vector<vector<int> > vodorovne_dialnice, zvisle_dialnice;

    for (const auto &it1: YX)
    {
        //hladame po riadkoch vodorovne dialnice
        int y = it1.first;
        auto it_next = it1.second.begin();
        int x_zac = -1;
        for (auto it2 = it_next++; ; it2 = it_next++) {
            if (x_zac == -1) {
                x_zac = it2->first;
            }

            // ak uz dalej ziadna krizovatka nie je tak dialnicu skoncime
            bool skonci = it_next == it1.second.end();

            //skoncime ju aj ked dalsi usek sa nam neoplati postavit
            if(!skonci)
            {
                dialnicny_usek usek = {it_next->first, y, false};
                skonci = nepostavime.count(usek);
            }

            //ked skoncime tak sme nasli koniec a ten si zapiseme
            if (skonci)
            {
                vodorovne_dialnice.push_back({x_zac, y, it2->first, y});
                x_zac = -1;
            }
            if (it_next == it1.second.end()) break;
        }
    }

    for (const auto &it1: XY)
    {
        //hladame po stlpcoch zvisle dialnice
        int x = it1.first;
        auto it_next = it1.second.begin();
        int y_zac = -1;
        for (auto it2 = it_next++; ; it2 = it_next++) {
            if (y_zac == -1) {
                y_zac = it2->first;
            }

            // ak uz dalej ziadna krizovatka nie je tak dialnicu skoncime
            bool skonci = it_next == it1.second.end();

            //skoncime ju aj ked dalsi usek sa nam neoplati postavit
            if(!skonci)
            {
                dialnicny_usek t = {x, it_next->first, true};
                skonci =  nepostavime.count(t);
            }

            //ked skoncime tak sme nasli koniec a ten si zapiseme
            if (skonci)
            {
                zvisle_dialnice.push_back({x, y_zac, x, it2->first});
                y_zac = -1;
            }
            if (it_next == it1.second.end()) break;
        }
    }

    printf("%d\n", vodorovne_dialnice.size());
    for(auto x: vodorovne_dialnice)
        printf("%d %d %d %d\n", x[0], x[1], x[2], x[3]);
    printf("%d\n", zvisle_dialnice.size());
    for(auto x: zvisle_dialnice)
        printf("%d %d %d %d\n", x[0], x[1], x[2], x[3]);

}