Pagini recente » Cod sursa (job #2240984) | Cod sursa (job #2805478) | Cod sursa (job #52305) | Cod sursa (job #2698883) | Cod sursa (job #1895425)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int inf = 1e9;
#define nmax 805
#define mp make_pair
#define f first
#define s second
priority_queue <pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > >q;
vector <int> v[nmax];
pair<int,int> pozs[nmax];
pair<int,int> poza[nmax];
double cst[nmax][nmax];
int c[nmax][nmax];
int f[nmax][nmax];
double d[nmax];
int t[nmax];
double ans,cost;
int mn,a,b,n;
inline double ab(double x)
{
if(x<0)
return -x;
return x;
}
double dist(pair<int,int> a,pair<int,int> b)
{
return (double)sqrt((a.f-b.f)*(a.f-b.f)+(a.s-b.s)*(a.s-b.s));
}
bool dijkstra(double mx)
{
for(int i=1; i<=b; ++i)
d[i]=inf;
d[a]=0;
q.push(mp(0,a));
while(!q.empty())
{
int nod = q.top().s;
double curr = q.top().f;
q.pop();
if(curr!=d[nod])
continue;
for(auto it:v[nod])
if(ab(cst[nod][it])<=mx && d[nod]+cst[nod][it]<d[it] && c[nod][it]!=f[nod][it])
{
d[it]=d[nod]+cst[nod][it];
t[it]=nod;
q.push(mp(d[it],it));
}
}
return d[b]!=inf;
}
int flux(int mx)
{
memset(f, 0, sizeof(f));
cost = 0;
int maxflow = 0;
while(dijkstra(mx))
{
int flow = inf;
for(int i=b; i!=a; i=t[i])
flow=min(flow,c[t[i]][i]-f[t[i]][i]);
for(int i=b; i!=a; i=t[i])
{
f[t[i]][i]+=flow;
f[i][t[i]]-=flow;
cost+=(double)flow*cst[t[i]][i];
}
maxflow+=flow;
}
return maxflow;
}
void bs()
{
mn = 100000000;
int p=1;
for( ; p<mn; p<<=1);
for( ; p; p>>=1)
if(mn-p>0 && flux(mn-p)==n)
{
mn-=p;
ans=cost;
}
}
int main()
{
fin>>n;
int i,j;
for(i=1; i<=n; ++i)
{
float a,b;
fin>>a>>b;
pozs[i]=mp(a*1000,b*1000);
}
for(i=1; i<=n; ++i)
{
float a,b;
fin>>a>>b;
poza[i]=mp(a*1000,b*1000);
}
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
{
c[i][j+n]=1;
cst[i][j+n]=dist(pozs[i],poza[j]);
cst[j+n][i]=-cst[i][j+n];
v[i].push_back(j+n);
v[j+n].push_back(i);
}
a = 0;
b = 2*n+1;
for(i=1; i<=n; ++i)
{
c[a][i]=1;
v[a].push_back(i);
}
for(i=1; i<=n; ++i)
{
c[n+i][b]=1;
v[n+i].push_back(b);
}
bs();
fout<<(double)mn/1000<<' '<<(double)ans/1000;
}