Pagini recente » Cod sursa (job #478808) | Cod sursa (job #420386)
Cod sursa(job #420386)
using namespace std;
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
#include<queue>
#define pb push_back
#define oo 0x3f3f3f3f
const int MAX_N = 805;
vector<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];
double CST, LIM, cin[MAX_N][MAX_N];
int st[MAX_N], dr[MAX_N];
double d[MAX_N], A[401*402], X[MAX_N], Y[MAX_N];
inline double dist(double &a, double &b, double &c, double &d)
{
return sqrt( (a - c)*(a-c) + (b-d)*(b-d) );
}
short int tata[MAX_N];
struct cmp
{
bool operator()(const int &a, const int &b)
{
return d[a]>d[b];
}
};
int BFS()
{
int x, y, i;
priority_queue <int, vector <int>, cmp > Q;
for(i = 0; i <= D; ++i) d[i] = oo, tata[i] = 0, viz[i]=0;
d[S] = 0;
Q.push(S);
while( !Q.empty() )
{
x = Q.top(); viz[x] = 0; Q.pop();
for(i = 0; i < G[x].size(); ++i)
{
y = G[x][i];
if( capac[x][y]!=0 && d[y] > d[x] + cst[x][y])
{
d[y] = d[x] + cst[x][y];
tata[y] = x;
if(viz[y]) continue;
Q.push(y);
viz[y] = 1;
}
}
}
if( d[D] == oo ) return 0;
return 1;
}
void flux()
{
int i;
for(;BFS();)
{
for(i = D; i != S; i =tata[i])
{
capac[tata[i]][i] --;
capac[i][tata[i]] ++;
}
CST += d[D];
}
}
int pairUp(int x)
{
if(viz[x]) return 0;
int y; unsigned i;
viz[x] = 1;
for(i = 0; i < G[x].size(); ++i)
{
y = G[x][i];
if( !st[y] )
{
st[y] = x;
dr[x] = y;
return 1;
}
}
for(i = 0; i < G[x].size(); ++i)
{
y = G[x][i];
if( pairUp(st[y]) )
{
st[y] = x;
dr[x] = y;
return 1;
}
}
return 0;
}
void limiteaza(double L)
{
int i, j;
for(i = 1; i <= N; ++i)
{
G[i].clear();
for(j = 1; j <= N; ++j)
if( cin[i][j+N] <= L )
{
G[i].pb(j+N); G[j+N].pb(i);
cst[i][j+N] = cin[i][j+N]; cst[j+N][i] = - cst[i][j+N];
capac[i][j+N] = 1;
}
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);
}
}
inline int pot(double lim)
{
for(int i = 1; i <= N; ++i)
{
G[i].clear();
for(int j = 1; j <= N; ++j)
if(lim >= cin[i][j+N])
G[i].push_back(j+N);
}
int nr = 0, i, ok;
memset(st,0,sizeof(st));
memset(dr,0,sizeof(dr));
for(ok = 1; ok;)
{
ok = 0;
memset(viz, 0, sizeof(viz));
for(i = 1; i <= N; ++i)
if( !dr[i] ) ok|=pairUp(i);
}
for(i = 1; i <= N; ++i)
if(dr[i]) ++nr;
if(nr == N) return 1;
return 0;
}
int main()
{
ifstream in("adapost.in"); ofstream out("adapost.out");
int i, j;
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;
for(j = 1; j <= N; ++j)
{
d = dist(x, y, X[j], Y[j]);
cin[i][j+N] = d;
capac[i][j + N] = 1;
A[P++] = d;
}
}
sort(A, A + P);
int step;
for(step=1; step<=P;step<<=1);
for(i = P - 1; step; step>>=1)
if( i - step >= 0 && pot( A[i - step] ) )
i -= step;
limiteaza(A[i]); CST = 0;
flux();
out<<setprecision(5)<<fixed<<A[i]<<" "<<CST<<"\n";
return 0;
}