Pagini recente » Cod sursa (job #859309) | Cod sursa (job #2534322) | Cod sursa (job #934021) | Cod sursa (job #55317) | Cod sursa (job #1871992)
#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 int Inf = 0x3f3f3f3f;
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;
void ReadAndBuildGraph();
bool PairUp( int x );
bool Verif( int ld );
double Minim();
int main()
{
ReadAndBuildGraph();
fout << Minim() << ' ';
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] = 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) );
dist.push_back(d[i][j]);
G[i].push_back(j + n);
G[j + n].push_back(i);
}
sort( dist.begin(), dist.end() );
}
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] - dmax <= eps )
{
l[x] = i;
r[i] = x;
return true;
}
}
for ( int i = 1; i <= n; ++i )
if ( d[x][i] - 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;
}