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;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

typedef double Weight;

struct Edge {
    ll to, cap;
    Weight cost;
    ll rev;
};

vector< vector<Edge> > G;

void add_edge(ll from, ll to, ll cap, Weight cost) {
    if (from < 0 || to < 0) return;
    G[from].push_back({to, cap, cost, (ll)G[to].size()});
    G[to].push_back({from, 0, -cost, (ll)G[from].size()-1});
}

Weight dist[21000], h[21000] = {0};
ll prevV[21000], prevE[21000];
double min_cost_flow(ll s, ll t, ll f) {
    typedef pair<Weight, ll> _P;
    Weight res = 0;
    while (f > 0) {
        fill_n(dist, 21000, inf); dist[s] = 0;
        priority_queue<_P, vector<_P>, greater<_P> > Q; Q.push({0, s});
        while ( !Q.empty() ) {
            _P p = Q.top(); Q.pop();
            ll v = p.second;
            if (p.first > dist[v]) continue;
            REP(i, G[v].size()) {
                Edge& e = G[v][i];
                if (e.cap > eps && dist[v]+e.cost+h[v]-h[e.to]+eps < dist[e.to]) {
                    dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
                    prevV[e.to] = v;
                    prevE[e.to] = i;
                    Q.push({dist[e.to], e.to});
                }
            }
        }
        REP(i, G.size()) h[i] += dist[i];

        if (abs(dist[t]-inf) < eps) {
            cout << "ERROR" << endl;
            exit(1);
        }

        ll d = f;
        for (ll v = t; v != s; v = prevV[v]) {
            d = min(d, G[prevV[v]][prevE[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for (ll v = t; v != s; v = prevV[v]) {
            Edge& e = G[prevV[v]][prevE[v]];
            e.cap -= d;
            G[e.to][e.rev].cap += d;
        }
    }
    return res;
}

typedef complex<double> Point;
template <typename T>
istream& operator>>(istream& is, complex<T>& p) {
    T x, y; is >> x >> y;
    p = {x, y};
    return is;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    Point sp; cin >> sp;
    vector<pair<Point,Point>> v(n);
    REP(i, n) cin >> v[i].first >> v[i].second;
    double ans = 0;
    REP(i, n) ans += abs(v[i].second-v[i].first);
    int lid = 0;
    vector<int> fid(n), tid(n);
    REP(i, n) fid[i] = lid++;
    REP(i, n) tid[i] = lid++;
    int s = lid++, t = lid++;
    G.clear(); G.resize(lid);
    REP(i, n) REP(j, n) {
        double cost = abs(v[i].second-v[j].first);
        add_edge(fid[i], tid[j], 1, cost);
    }
    REP(i, n) add_edge(s, fid[i], 1, 0);
    REP(i, n) add_edge(tid[i], t, 1, 0);
    ans += min_cost_flow(s, t, n);
    cout << fixed << setprecision(10) << ans << endl;
}