Pagini recente » Cod sursa (job #848771) | Cod sursa (job #1161947) | Cod sursa (job #3227059) | Cod sursa (job #3239571) | Cod sursa (job #3155098)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream in ("adapost.in");
ofstream out ("adapost.out");
const int max_size = 8e2 + 9;
const double INF = 1e9 + 1;
struct str{
int nod;
double val;
bool operator < (const str &aux) const
{
return val > aux.val;
}
};
#define pdd pair <double, double>
double cap[max_size][max_size], cost[max_size][max_size], d[max_size][max_size], dist[max_size], pr[max_size], aux[max_size];
int t[max_size], dr[max_size], st[max_size], n;
pdd sld[max_size], adp[max_size];
bitset <max_size> viz;
vector <int> mc[max_size];
queue <int> q;
priority_queue <str> pq;
void bf ()
{
for (int i = 1; i <= 2 * n + 2; i++)
{
aux[i] = INF;
viz[i] = 0;
}
aux[1] = 0;
q.push(1);
while (!q.empty())
{
int nod = q.front();
q.pop();
viz[nod] = 0;
for (auto f : mc[nod])
{
if (aux[nod] + cost[nod][f] < aux[f] && cap[nod][f] > 0)
{
aux[f] = aux[nod] + cost[nod][f];
if (viz[f] == 0)
{
viz[f] = 1;
q.push(f);
}
}
}
}
}
bool djk ()
{
for (int i = 1; i <= 2 * n + 2; i++)
{
dist[i] = INF;
pr[i] = INF;
t[i] = 0;
}
dist[1] = 0;
pr[1] = 0;
pq.push({1, 0});
while (!pq.empty())
{
int nod = pq.top().nod;
double val = pq.top().val;
pq.pop();
if (val > dist[nod])
{
continue;
}
for (auto f : mc[nod])
{
if (cap[nod][f] > 0 && dist[nod] + cost[nod][f] + aux[nod] - aux[f] < dist[f])
{
dist[f] = dist[nod] + cost[nod][f] + aux[nod] - aux[f];
pr[f] = pr[nod] + cost[nod][f];
t[f] = nod;
pq.push({f, dist[f]});
}
}
}
return (dist[2 * n + 2] != INF);
}
bool pairup (int nod)
{
if (viz[nod])
{
return false;
}
viz[nod] = 1;
for (auto f : mc[nod])
{
if (dr[f] == 0)
{
st[nod] = f;
dr[f] = nod;
return true;
}
}
for (auto f : mc[nod])
{
if (pairup(dr[f]))
{
st[nod] = f;
dr[f] = nod;
return true;
}
}
return false;
}
bool verif (double x)
{
for (int i = 1; i <= 2 * n + 2; i++)
{
mc[i].clear();
}
for (int i = 1; i <= n; i++)
{
st[i + 1] = 0;
st[i + n + 1] = 0;
dr[i + 1] = 0;
dr[i + n + 1] = 0;
for (int j = 1; j <= n; j++)
{
if (d[i][j] <= x)
{
mc[i + 1].push_back(n + j + 1);
mc[n + j + 1].push_back(i + 1);
}
}
}
bool ok = false;
while (1)
{
for (int i = 1; i <= 2 * n + 2; i++)
{
viz[i] = 0;
}
ok = false;
for (int i = 2; i <= n + 1; i++)
{
if (!st[i])
{
ok |= pairup(i);
}
}
if (!ok)
{
break;
}
}
int ct = 0;
for (int i = 2; i <= n + 1; i++)
{
if (st[i] > 0)
{
ct++;
}
}
return (ct == n);
}
int main ()
{
in >> n;
for (int i = 1; i <= n; i++)
{
in >> sld[i].first >> sld[i].second;
}
for (int i = 1; i <= n; i++)
{
in >> adp[i].first >> adp[i].second;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
d[i][j] = sqrt((sld[i].first - adp[j].first) * (sld[i].first - adp[j].first) + (sld[i].second - adp[j].second) * (sld[i].second - adp[j].second));
}
}
double l = 0, r = 2000, costmc = 0;
while (r - l > 0.0001)
{
double m = (l + r) / 2;
if (verif(m))
{
r = m;
costmc = m;
}
else
{
l = m;
}
}
out << fixed << setprecision(5) << costmc << " ";
for (int i = 1; i <= 2 * n + 2; i++)
{
mc[i].clear();
}
for (int i = 1; i <= n; i++)
{
mc[1].push_back(i + 1);
mc[i + 1].push_back(1);
cap[1][i + 1] = 1;
for (int j = 1; j <= n; j++)
{
if (d[i][j] <= costmc)
{
mc[i + 1].push_back(j + n + 1);
mc[j + n + 1].push_back(i + 1);
cap[i + 1][j + n + 1] = 1;
cost[i + 1][j + n + 1] = d[i][j];
cost[j + n + 1][i + 1] = -d[i][j];
}
}
}
for (int j = n + 2; j <= 2 * n + 1; j++)
{
cap[j][2 * n + 2] = 1;
mc[j].push_back(2 * n + 2);
mc[2 * n + 2].push_back(j);
}
bf();
double ans = 0;
while (djk())
{
//out << "*";
int nod = 2 * n + 2;
ans += pr[2 * n + 2];
while (nod != 1)
{
cap[t[nod]][nod]--;
cap[nod][t[nod]]++;
nod = t[nod];
}
for (int i = 1; i <= 2 * n + 2; i++)
{
aux[i] = dist[i];
}
}
out << fixed << setprecision(5) << ans;
in.close();
out.close();
return 0;
}