Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <sstream>
- #include <utility>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <fstream>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <queue>
- #include <cmath>
- #include <ctime>
- #include <stack>
- #include <map>
- #include <set>
- using namespace std;
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define N 50
- #define f first
- #define s second
- #define abs(a) ((a) < 0 ? -(a) : (a))
- #define sqr(a) ((a) * (a))
- typedef unsigned int uint;
- typedef long long ll;
- typedef unsigned long long ull;
- const double eps = 1e-9;
- const int mod = (int)1e+9 + 7;
- const double pi = acos(-1.);
- const int maxn = 5000;
- #define inf (1ll << 30)
- char ch;
- ll x, y, z, n, m;
- double d[maxn];
- int s, t;
- bool was[maxn];
- pair <int, pair <int, int> > p[maxn];
- pair <int, int> a[maxn], b[maxn];
- double pot[1000];
- int q[int(1e6)];
- bool inqueue[int(1e6)];
- struct Edge{
- int to, cap, flow;
- double cost;
- int id;
- };
- vector <Edge> g[maxn];
- set < pair < double, int > > qe;
- bool djikstra(int s, int t) {
- for (int i = 0; i <= t + 10; i++) {
- d[i] = inf;
- was[i] = 0;
- }
- d[s] = 0;
- qe.clear();
- qe.insert(mp(d[s], s));
- while (!qe.empty()) {
- int v = qe.begin()-> second;
- qe.erase(qe.begin());
- for (int j = 0; j < g[v].size(); j++) {
- int to = g[v][j].to;
- double cost = g[v][j].cost;
- int cap = g[v][j].cap;
- int fl = g[v][j].flow;
- if (cap - fl > 0 && d[to] > d[v] + cost + pot[v] - pot[to]) {
- qe.erase(mp(d[to], to));
- d[to] = d[v] + cost + pot[v] - pot[to];
- qe.insert(mp(d[to], to));
- p[to] = mp(v, mp(cap-fl, j));
- }
- }
- }
- for (int i = 0; i <= t; i++)
- if (d[i] != inf)
- pot[i] += d[i];
- return d[t] != inf;
- }
- double res = 0;
- double getans(int x) {
- if (x == 0) return 0;
- if (x < 0) {
- return (sqrt(-x));
- }
- return sqrt(x);
- }
- void add(int v, int t, int cap, int fl, double cost) {
- Edge e1;
- e1.to = t;
- e1.cap = cap;
- e1.flow = fl;
- e1.cost = cost;
- e1.id = g[t].size();
- Edge e2;
- e2.to = v;
- e2.cap = 0;
- e2.id = g[v].size();
- e2.flow = 0;
- e2.cost = -cost;
- g[v].pb(e1);
- g[t].pb(e2);
- }
- double flow(int s, int t) {
- int v = t;
- int fl = int(1e9);
- while (v != s) {
- fl = min(fl, p[v].s.f);
- v = p[v].f;
- }
- v = t;
- while (v != s) {
- g[p[v].f][p[v].s.s].flow += fl;
- g[v][g[p[v].f][p[v].s.s].id].flow -= fl;
- res += fl * g[p[v].f][p[v].s.s].cost;
- v = p[v].f;
- }
- return 0;
- }
- double dist(int xa, int ya, int xb, int yb) {
- return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
- }
- int get(int xa, int ya, int xb, int yb) {
- return (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
- }
- int main() {
- scanf("%d%d%d", &n, &x, &y);
- for (int i = 1; i <= n; i++) {
- scanf("%d%d%d%d", &a[i].f, &b[i].f, &a[i].s, &b[i].s);
- //cin >> a[i].f >> b[i].f >> a[i].s >> b[i].s;
- res += dist(a[i].f, b[i].f, a[i].s, b[i].s);
- }
- s = 0, t = n + n + 1;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- add(i, n + j, 1, 0, dist(a[i].s, b[i].s, a[j].f, b[j].f));
- for (int i = 1; i <= n; i++)
- add(0, i, 1, 0, 0);
- for (int i = 1; i <= n; i++)
- add(n + i, t, 1, 0, 0);
- while (djikstra(s, t)) {
- flow(s, n + n + 1);
- }
- printf("%.10lf", res);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement