Pagini recente » Cod sursa (job #1897249) | Cod sursa (job #2952300) | Cod sursa (job #1661168) | Cod sursa (job #1306844) | Cod sursa (job #402572)
Cod sursa(job #402572)
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
const int MAX_N = 405;
const double eps = 0.00001;
int N, M, C[MAX_N], R[MAX_N];
pair <double, double> S[MAX_N], A[MAX_N];
double L[MAX_N][MAX_N], T[MAX_N * MAX_N];
char viz[MAX_N];
vector <int> G[MAX_N];
inline double dist(pair <double, double> &a, pair <double, double> &b)
{
double dx = (a.x - b.x) * (a.x - b.x);
double dy = (a.y - b.y) * (a.y - b.y);
return sqrt(dx + dy);
}
void citire()
{
scanf("%d\n", &N);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf\n", &S[i].x, &S[i].y);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf\n", &A[i].x, &A[i].y);
for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= N; ++j)
{
L[i][j] = dist(S[i], A[j]);
T[++M] = L[i][j];
// fprintf(stderr, "%lf ", L[i][j]);
}
// fprintf(stderr, "\n");
}
}
bool pairup(int nod)
{
if(viz[nod]) return 0;
viz[nod] = 1;
foreach(G[nod])
if(!R[*it])
{
C[nod] = *it;
R[*it] = nod;
return 1;
}
foreach(G[nod])
if(pairup(R[*it]))
{
C[nod] = *it;
R[*it] = nod;
return 1;
}
return 0;
}
inline bool cuplaj(double x)
{
for(int i = 1; i <= N; ++i)
{
G[i].clear();
// fprintf(stderr, "%d : ", i);
for(int j = 1; j <= N; ++j)
if(x - L[i][j] > eps || abs(x - L[i][j]) < eps)
{
G[i].push_back(j);
// fprintf(stderr, "%d ", j);
}
// fprintf(stderr, "\n");
}
memset(C, 0, sizeof C);
memset(R, 0, sizeof R);
bool ok = 1;
while(ok)
{
ok = 0;
memset(viz, 0, sizeof viz);
for(int i = 1; i <= N; ++i)
if(!C[i])
ok |= pairup(i);
}
for(int i = 1; i <= N; ++i)
if(!C[i])
return 0;
return 1;
}
int main()
{
freopen("adapost.in", "rt", stdin);
freopen("adapost.out", "wt", stdout);
citire();
sort(T+1, T+M+1);
int i = M;
for(int lg = 18; lg; lg >>= 1)
if(i - lg > 0 && cuplaj(T[i-lg]))
i -= lg;
//cuplaj(T[1]);
printf("%lf\n", T[i]);
}