Pagini recente » Cod sursa (job #1660005) | Cod sursa (job #1590543) | Cod sursa (job #1669074) | Cod sursa (job #2648204) | Cod sursa (job #1872038)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int MAX = 2*405;
const double Inf = 99999999.;
const double eps = 0.0001;
struct Nod{
int nod, cost;
bool operator < ( const Nod& a )
{
return cost > a.cost;
}
};
using VI = vector<int>;
using VF = vector<double>;
vector<int> G[MAX];
VI l, r, u;
vector<pair<double, double>> s, a;
int n, N;
double d[MAX][MAX];
double dmax;
VF dist;
int C[MAX][MAX];
int F[MAX][MAX];
VF Cost;
double rez;
void ReadAndBuildGraph();
bool PairUp( int x );
bool Verif( int ld );
double Minim();
bool Bellman_Ford();
double Abs( double x )
{
if ( x >= 0 ) return x;
return -x;
}
int main()
{
ReadAndBuildGraph();
double c1 = Minim();
fout << c1 << ' ';
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
if ( d[i][j + n] - c1 <= eps )
{
G[i].push_back(j + n);
G[j + n].push_back(i);
C[i][j + n] = 1;
}
while ( Bellman_Ford() );
fout << rez << '\n';
fin.close();
fout.close();
return 0;
}
void ReadAndBuildGraph()
{
int x, y;
fin >> n; N = 2*n + 1;
s = a = vector<pair<double, double>>(n + 1);
for ( int i = 1; i <= n; ++i )
fin >> s[i].first >> s[i].second;
for ( int i = 1; i <= n; ++i )
fin >> a[i].first >> a[i].second;
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
{
d[i][j + n] = sqrt( (a[j].first - s[i].first)*(a[j].first - s[i].first) + (a[j].second - s[i].second)*(a[j].second - s[i].second) );
d[j + n][i] = -d[i][j + n];
dist.push_back(d[i][j + n]);
}
sort( dist.begin(), dist.end() );
for ( int i = 1; i <= n; ++i )
{
G[0].push_back(i);
G[i].push_back(0);
C[0][i] = 1;
}
for ( int i = n + 1; i < N; ++i )
{
G[i].push_back(N);
G[N].push_back(i);
C[i][N] = 1;
}
}
bool PairUp( int x )
{
if ( u[x] ) return false;
u[x] = 1;
for ( int i = 1; i <= n; ++i )
{
if ( !r[i] && d[x][i + n] - dmax <= eps )
{
l[x] = i;
r[i] = x;
return true;
}
}
for ( int i = 1; i <= n; ++i )
if ( d[x][i + n] - dmax <= eps )
if ( PairUp(r[i]) )
{
l[x] = i;
r[i] = x;
return true;
}
return false;
}
bool Verif( int ld )
{
dmax = dist[ld];
bool change;
l = r = VI(n + 1);
do
{
change = false;
u = VI(n + 1, 0);
for ( int i = 1; i <= n; ++i )
if ( !l[i] )
change |= PairUp(i);
}while ( change );
for ( int i = 1; i <= n; ++i )
if ( !l[i] )
return false;
return true;
}
double Minim()
{
int st = 0, dr = dist.size() - 1, mij;
double rez;
while ( st <= dr )
{
mij = ( st + dr ) / 2;
if ( Verif(mij) )
{
dr = mij - 1;
rez = dist[mij];
}
else
st = mij + 1;
}
return rez;
}
bool Bellman_Ford()
{
queue<int> Q;
Cost = VF(N + 1, Inf);
VI t(N + 1);
Cost[0] = 0;
Q.push(0);
while ( !Q.empty() )
{
int x = Q.front();
Q.pop();
for ( const int& y : G[x] )
if ( C[x][y] - F[x][y] > 0 )
{
double c_nou = Cost[x] + d[x][y];
if ( Cost[y] - c_nou <= eps ) continue;
Cost[y] = c_nou;
t[y] = x;
Q.push(y);
}
}
if ( Abs(Cost[N] - Inf) <= eps )
return false;
/* for ( int i = 1; i <= N; ++i )
cout << i << " : " << Cost[i] << '\n';
cin.get(); */
rez += Cost[N];
for ( int i = N; i != 0; i = t[i] )
{
F[t[i]][i]++;
F[i][t[i]]--;
}
return true;
}