Pagini recente » Cod sursa (job #2791957) | Cod sursa (job #1124357) | Cod sursa (job #870088) | Cod sursa (job #1562662) | Cod sursa (job #64881)
Cod sursa(job #64881)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define NMAX 404
#define INF 666000666
#define eps 1e-4
#define f first
#define s second
using namespace std;
int N, Cup[NMAX], F[NMAX];
vector<pair<double,int> > D[NMAX];
double X[NMAX], Y[NMAX], Rmin, Dmin, Dd[NMAX][NMAX];
void read()
{
int i, j;
double x, y;
freopen("adapost.in", "r", stdin);
scanf("%d", &N);
for (i = 1; i <= N; i++)
{ scanf("%lf %lf", &X[i], &Y[i]); D[i].push_back(make_pair(-INF,0)); }
for (i = 1; i <= N; i++)
{
scanf("%lf %lf", &x, &y);
for (j = 1; j <= N; j++)
{
D[j].push_back(make_pair(sqrt( (X[j]-x)*(X[j]-x) + (Y[j]-y)*(Y[j]-y) ), i));
Dd[j][i] = D[j][i].f;
}
}
for (i = 1; i <= N; i++) sort(D[i].begin(), D[i].end());
}
int pairthembaby(int i, double dmax)
{
int j;
if (F[i]) return 0;
F[i] = 1;
for (j = 1; j <= N && D[i][j].f <= dmax; j++)
if ((!Cup[ D[i][j].s ]) || (pairthembaby(j, dmax)))
{
Cup[ D[i][j].s ] = i;
return 1;
}
return 0;
}
void joint(double dmax)
{
int i;
for (i = 1; i <= N; i++)
if (!pairthembaby(i,dmax))
{
memset(F,0,sizeof(F));
pairthembaby(i,dmax);
}
}
void solve()
{
int flow, i;
double lo = 0, hi = (1<<28), mij, dist;
while (lo<=hi)
{
mij = (lo+hi)/2.0;
memset(Cup,0,sizeof(Cup));
joint(mij);
for (i = 1, dist = flow = 0; i <= N; i++)
dist += Dd[ Cup[i] ][i], flow += (Cup[i]>0);
if (flow == N) Rmin = mij, Dmin = dist, hi = mij-eps;
else lo = mij+eps;
}
}
void write()
{
freopen("adapost.out", "w", stdout);
printf("%lf %lf\n", Rmin, Dmin);
}
int main()
{
read();
solve();
write();
return 0;
}