Pagini recente » Cod sursa (job #1452186) | Cod sursa (job #78978) | Cod sursa (job #1402532) | Cod sursa (job #2715490) | Cod sursa (job #3202815)
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif
using namespace std;
#ifndef LOCAL
ifstream in("adapost.in");
ofstream out("adapost.out");
#endif
const int nmax = 405;
int n;
pair<double, double> p1[nmax], p2[nmax];
struct line
{
int i, j;
double dist;
line(int i = 0, int j = 0) : i(i), j(j)
{
double x = abs(p1[i].first - p2[j].first);
double y = abs(p1[i].second - p2[j].second);
dist = sqrt(x * x + y * y);
}
bool operator<(const line &other)
{
return dist < other.dist;
}
void debug()
{
cerr << i << ' ' << j << ' ' << dist << '\n';
}
} lines[nmax * nmax];
double biadj[nmax][nmax];
int l[nmax], r[nmax];
bool viz[nmax];
bool pairup(int nod, double upp)
{
if (viz[nod])
return 0;
viz[nod] = 1;
for (int i = 0; i < n; i++)
{
if (biadj[nod][i] <= upp)
{
if (l[i] == -1)
{
l[i] = nod;
r[nod] = i;
return 1;
}
}
}
for (int i = 0; i < n; i++)
{
if (biadj[nod][i] <= upp)
{
if (pairup(l[i], upp))
{
l[i] = nod;
r[nod] = i;
return 1;
}
}
}
return 0;
}
bool bipart(double upperbound)
{
for (int i = 0; i < n; i++)
{
l[i] = -1;
r[i] = -1;
}
bool change = 0;
int pairs = 0;
do
{
change = 0;
memset(viz, 0, sizeof viz);
for (int i = 0; i < n; i++)
{
if (r[i] == -1)
{
if (pairup(i, upperbound))
{
change = 1;
pairs++;
}
}
}
} while (change);
return pairs == n;
}
int main()
{
in >> n;
for (int i = 0; i < n; i++)
{
in >> p1[i].first >> p1[i].second;
}
for (int i = 0; i < n; i++)
{
in >> p2[i].first >> p2[i].second;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
lines[i * (n) + j] = line(i, j);
biadj[i][j] = lines[i * (n) + j].dist;
}
sort(lines, lines + (n * n));
int st = 0, dr = n * n - 1;
while (st < dr)
{
int mid = (st + dr) / 2;
if (bipart(lines[mid].dist))
{
dr = mid;
}
else
{
st = mid + 1;
}
}
double upp = lines[st].dist;
out<<upp<<' ';
}