Problem: Example

Input

3
0 1
0 0 0 1
0 1 0 2
0 2 0 3


Output

6.0000000000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

template<class D>
struct Hungarian {
    V<D> le, ri;
    V<int> perm;

    Hungarian(const VV<D> &c) {
        int n = int(c.size()), m = int(c[0].size());
        assert(n <= m);
        le = V<D>(n, D(0)); ri = V<D>(m, D(0));
        perm = V<int>(n);
        V<int> tori(n, -1), tole(m, -1);

        auto cost = [&](int l, int r) { return c[l][r] + le[l] + ri[r]; };
        for (int l = 0; l < n; l++) {
            V<bool> leu(n), riu(m);
            V<int> tr(m, -1), mai(m, l);
            leu[l] = true;

            while (true) {
                int b = -1;
                D d = numeric_limits<D>::max();
                for (int j = 0; j < m; j++) {
                    if (!riu[j] && cost(mai[j], j) < d) {
                        b = j;
                        d = cost(mai[j], j);
                    }
                }
                for (int i = 0; i < n; i++) if (leu[i]) le[i] -= d;
                for (int j = 0; j < m; j++) if (riu[j]) ri[j] += d;
                tr[b] = mai[b];
                int c = tole[b];
                if (c == -1) {
                    while (b != -1) {
                        int a = tr[b], z = tori[a];
                        tole[b] = a;
                        tori[a] = b;
                        b = z;
                    }
                    break;
                }
                riu[b] = leu[c] = true;
                for (int j = 0; j < m; j++) {
                    if (cost(c, j) < cost(mai[j], j)) {
                        mai[j] = c;
                    }
                }
            }
        }
        perm = tori;
    }    
};

using D = double;
const D PI = acos(D(-1)), EPS = 1e-10;

int sgn(D a) { return (abs(a) <= EPS) ? 0 : (a < 0 ? -1 : 1); }
int sgn(D a, D b) { return sgn(a-b); }

struct Pt2 {
    D x, y;
    Pt2() {}
    Pt2(D _x, D _y) : x(_x), y(_y) {}
    Pt2 operator-(const Pt2 &r) const { return Pt2(x-r.x, y-r.y); }
    bool operator<(const Pt2 &r) const { return 2*sgn(x, r.x)+sgn(y, r.y)<0; }
    bool operator==(const Pt2 &r) const { return sgn((*this-r).rabs()) == 0; }
    D abs() const { return sqrt(x*x + y*y); }
    D rabs() const { return max(std::abs(x), std::abs(y)); }
};
ostream& operator<<(ostream& os, const Pt2 &p) {
    return os << "(" << p.x << ", " << p.y << ")";
}
using P = Pt2;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;

    D ans = 0;

    int n;
    cin >> n;
    D x, y;
    P p;
    cin >> x >> y; p = P(x, y);
    map<P, int> mp;
    for (int i = 0; i < n; i++) {
        P p, q;
        cin >> x >> y; p = P(x, y);
        mp[p]++;
        cin >> x >> y; q = P(x, y);
        mp[q]--;
        ans += (p-q).abs();
    }

    V<P> up, dw;
    for (auto p: mp) {
        if (p.second == 0) continue;
        if (p.second > 0) {
            for (int i = 0; i < p.second; i++) {
                up.push_back(p.first);
            }
        } else {
            for (int i = 0; i < -p.second; i++) {
                dw.push_back(p.first);
            }
        }
    }

    int l = int(up.size()), r = int(dw.size());
    VV<D> cost(l, V<D>(r));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < r; j++) {
            cost[i][j] = (up[i] - dw[j]).abs();
        }
    }
    auto perm = Hungarian<D>(cost).perm;
    for (int i = 0; i < l; i++) {
        ans += cost[i][perm[i]];
    }
    cout << ans << endl;
    return 0;
}