Pagini recente » Cod sursa (job #2948014) | Cod sursa (job #2387347) | Cod sursa (job #160857) | Cod sursa (job #2919525) | Cod sursa (job #989823)
Cod sursa(job #989823)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#define x first
#define y second
#define newn a[x][i]
#define newnn g[x][i]
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int N = 410;
const int M = N * 2;
const int oo = 0x3f3f3f3f;
const double eps = 0.0001;
int s, d, n, nn, A[N], B[N], c[M][M], t[M];
typedef pair <double, double> pct;
double sol1, sol2, cst[M][M], cost[M][M], dist[M];
pct st[N], dr[N];
vector <int> a[M], g[M];
vector <bool> viz(N), inq(M);
queue <int> q;
double Dist(pct a, pct b)
{
return sqrt((b.x-a.x) * (b.x-a.x) + (b.y-a.y) * (b.y-a.y));
}
void Read()
{
fin>>n;
assert (n < 800);
for(int i=1; i<=n; i++)
fin>>st[i].x>>st[i].y;
for(int i=1; i<=n; i++)
fin>>dr[i].x>>dr[i].y;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cst[i][j] = Dist(st[i], dr[j]);
}
void Initialise(double lmax)
{
for(int i=1; i<=n; i++)
a[i].clear();
for(int i=1; i<=n; i++)
A[i] = B[i] = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(cst[i][j] < lmax)
a[i].push_back(j);
}
bool Pair(int x)
{
if(viz[x]) return 0;
for(unsigned i=0; i<a[x].size(); i++)
if(!B[newn])
{
A[x] = newn; B[newn] = x;
return 1;
}
for(unsigned i=0; i<a[x].size(); i++)
if(Pair(B[newn]))
{
A[x] = newn; B[newn] = x;
return 1;
}
return 0;
}
bool OK(double lmax)
{
Initialise(lmax);
bool ok = 1; int nr = 0;
while(ok)
{
ok = 0;
viz.assign(n+1, 0);
for(int i=1; i<=n; i++)
if(!A[i] && Pair(i)) ok = 1, nr++;
}
return nr == n;
}
void BS()
{
double up = 1420, dw = 0, mid;
while(up - dw > eps)
{
mid = (up + dw) / 2;
if(OK(mid))
up = mid;
else
dw = mid;
}
sol1 = up;
}
void Conect(int i, int j)
{
g[s].push_back(i);
g[j+n].push_back(d);
g[i].push_back(j+n);
g[j+n].push_back(i);
c[s][i] = 1; c[j+n][d] = 1;
cost[i][j+n] = cst[i][j];
cost[j+n][i] = -cst[i][j];
c[i][j+n] = 1;
}
void Build()
{
s = 0; d = 2 * n + 1; nn = d + 2;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(cst[i][j] <= sol1)
Conect(i, j);
}
bool Bellman_Ford()
{
inq.assign(nn, 0);
for(int i=0; i<nn; i++) dist[i] = oo;
dist[s] = 0; q.push(s); inq[s] = 1;
while(!q.empty())
{
int x = q.front(); inq[x] = 0; q.pop();
for(unsigned i=0; i<g[x].size(); i++)
if(c[x][newnn])
if(dist[x] + cost[x][newnn] < dist[newnn])
{
t[newnn] = x;
dist[newnn] = dist[x] + cost[x][newnn];
if(!inq[newnn]) inq[newnn] = 1, q.push(newnn);
}
}
return dist[d] != oo;
}
void Fmdcm()
{
while(Bellman_Ford())
{
for(int j=d; j!=s; j=t[j])
c[t[j]][j]--, c[j][t[j]]++;
sol2 += dist[d];
}
}
void Print()
{
fout<<fixed;
fout<<setprecision(5)<<sol1<<' '<<sol2;
}
int main()
{
Read();
BS();
//Build();
//Fmdcm();
Print();
}