Pagini recente » Cod sursa (job #1168867) | Cod sursa (job #1710581) | Cod sursa (job #2998981) | Cod sursa (job #2291552) | Cod sursa (job #419469)
Cod sursa(job #419469)
using namespace std;
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<queue>
#define pb push_back
#define EPS 1e-14
#define oo 0x3f3f3f3f
#include<vector>
const int MAX_N = 804;
vector<short int>G[MAX_N];
double cst[MAX_N][MAX_N];
short int capac[MAX_N][MAX_N];
int N,P, S, D;
bool viz[MAX_N]; queue<int>Q;
double CST, LIM;
double d[MAX_N], A[401*402], X[MAX_N], Y[MAX_N];
inline int comp(double a, double b)
{
if (a + EPS < b) return 1;
if (b + EPS < a) return -1;
return 0;
}
inline double dist(double a, double b, double c, double d)
{
return sqrt( (a - c)*(a-c) + (b-d)*(b-d) );
}
struct cmp
{
bool operator()(const double &a, const double &b)const
{
int r = comp(a,b);
if( r == 1) return 1;
return 0;
}
};
int tata[MAX_N];
int BFS()
{
int x, y, i;
for(i = 1; i <= D; ++i) d[i] = oo, viz[i] = false, tata[i] = 0;
for( Q.push(S); !Q.empty(); Q.pop() )
{
x = Q.front(); viz[x] = false;
for(i = 0; i < G[x].size(); ++i)
{
y = G[x][i];
if( capac[x][y] && cst[x][y] <= LIM && comp(d[y] , d[x] + cst[x][y]) == -1 )
{
d[y] = d[x] + cst[x][y];
tata[y] = x;
if( viz[y] ) continue;
viz[y] = true;
Q.push(y);
}
}
}
if( d[D] == oo ) return 0;
return 1;
}
void flux()
{
int i, f;
for(;BFS();)
{
f = oo;
for(i = D; i != S; i = tata[i])
if(f > capac[tata[i]][i]) f = capac[tata[i]][i];
for(i = D; i != S; i =tata[i])
{
capac[tata[i]][i] -=f;
capac[i][tata[i]] +=f;
}
CST += (double)f * d[D];
}
}
inline int pot(double lim)
{
CST = 0;
LIM = lim;
flux();
int nr = 0, i, j;
for(i = 1; i <= N; ++i)
for(j = N + 1; j <= 2*N; ++j)
if( capac[i][j] == 0) { ++nr; break; }
memset(capac, 0, sizeof(capac));
for(i = 1; i <= N; ++i)
{
for(j = N + 1; j <= 2*N; ++j)
capac[i][j] = 1;
capac[S][i] = capac[i+N][D] = 1;
}
if(nr == N) return 1;
return 0;
}
int main()
{
ifstream in("adapost.in"); ofstream out("adapost.out");
int st, dr, i, j, m, r, p;
double x,y, d;
in>>N;
S = 0; D = N + N + 1;
for(i = 1; i <= N; ++i) in>>X[i]>>Y[i];
for(i = 1; i <= N; ++i)
{
in>>x>>y;
capac[S][i] = 1; G[S].pb(i); G[i].pb(S);
capac[i+N][D] = 1; G[i+N].pb(D); G[D].pb(i+N);
for(j = 1; j <= N; ++j)
{
d = dist(x, y, X[j], Y[j]);
cst[i][j+N] = d; cst[j+N][i] = -d;
G[i].pb(j+N); G[j+N].pb(i);
capac[i][j + N] = 1;
A[P++] = d;
}
}
sort(A, A + P, cmp());
st = 0; dr = P - 1;
while(st<=dr)
{
m = (st + dr)>>1;
if(m) p = pot(A[m-1]);
else p = 0;
r = pot(A[m]);
if( r && !p )
{ out<<setprecision(5)<<fixed<<A[m]<<" "<<CST<<"\n"; return 0; }
else if( r && p ) dr = m - 1;
else st = m + 1;
}
return 0;
}