Pagini recente » Monitorul de evaluare | Cod sursa (job #2858271) | Cod sursa (job #2550211) | Cod sursa (job #1978055) | Cod sursa (job #603433)
Cod sursa(job #603433)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
#define maxn 810
#define inf 1000000000
#define maxq 640000
int n, i, j, k, tot;
pair<double, double> s[maxn], a[maxn];
double sol, ctot, sf, cost[maxn][maxn], dist[maxn];
int c[maxn][maxn], f[maxn][maxn], t[maxn], fol[maxn], q[maxn*maxn];
vector<int> v[maxn];
double distanta(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void build_graph(double mx)
{
memset(f, 0, sizeof(f));
memset(c, 0, sizeof(c));
for(int i=0; i<=2*n+1; ++i)
v[i].clear();
// printf("%.3lf\n", mx);
for(int i=1; i<=n; ++i)
{
c[0][i]=c[i+n][n*2+1]=1;
v[0].push_back(i);
v[i].push_back(0);
v[i+n].push_back(n*2+1);
v[n*2+1].push_back(i+n);
for(int j=1; j<=n; ++j)
if(!(cost[i][j+n]>mx))
{
// printf("*");
v[i].push_back(j+n);
v[j+n].push_back(i);
c[i][j+n]=1;
}
}
}
int flux()
{
memset(fol, 0, sizeof(fol));
int nod, fiu, qr=1;
q[qr]=0;
dist[i]=0;
fol[0]=1;
for(int i=1; i<=2*n+1; ++i)
dist[i]=inf;
for(int i=1; i<=qr; ++i)
{
nod=q[i%maxq];
fol[nod]=0;
for(int j=0; j<v[nod].size(); ++j)
{
fiu=v[nod][j];
if(c[nod][fiu]>f[nod][fiu] && dist[nod]+cost[nod][fiu]<dist[fiu])
{
t[fiu]=nod;
dist[fiu]=dist[nod]+cost[nod][fiu];
if(!fol[fiu])
{
fol[fiu]=1;
q[(++qr)%maxq]=fiu;
}
}
}
}
if(dist[2*n+1]==inf)
return 0;
int flx=inf;
nod=2*n+1;
while(nod)
{
flx=min(flx, c[t[nod]][nod]-f[t[nod]][nod]);
nod=t[nod];
}
tot+=flx;
ctot+=flx*dist[2*n+1];
nod=2*n+1;
while(nod)
{
f[t[nod]][nod]+=flx;
f[nod][t[nod]]-=flx;
nod=t[nod];
}
return 1;
}
int main()
{
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%lf%lf", &s[i].first, &s[i].second);
for(int i=1; i<=n; ++i)
scanf("%lf%lf", &a[i].first, &a[i].second);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
{
cost[i][j+n]=distanta(s[i].first, s[i].second, a[j].first, a[j].second);
cost[j+n][i]=-cost[i][j+n];
}
double med, left=0, right=1500;
for(int pas=1; pas<=30; ++pas)
{
med=(left+right)/2;
build_graph(med);
tot=0;
ctot=0;
while(flux());
if(tot==n)
{
sol=med;
sf=ctot;
right=med;
}
else
left=med;
}
printf("%.5lf %.5lf\n", sol, sf);
return 0;
}