Pagini recente » Cod sursa (job #2884374) | Cod sursa (job #1785570) | Cod sursa (job #2898288) | Cod sursa (job #1771765) | Cod sursa (job #1936525)
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#define pb push_back
using namespace std;
const int nmax=823;
int n;
vector<int>adj[nmax];
int sursa,dest,c[nmax][nmax],f[nmax][nmax],t[nmax],vis[nmax];
double soldier[2][nmax],refuge[2][nmax],dist[nmax][nmax],d[nmax],sol;
queue<int>q;
void citire()
{
scanf("%d",&n);
dest=2*n+1;
for(int i=1;i<=n;i++) scanf("%lf%lf",&soldier[0][i],&soldier[1][i]);
for(int i=1;i<=n;i++)
{
c[sursa][i]=1;
c[i+n][dest]=1;
scanf("%lf%lf",&refuge[0][i],&refuge[1][i]);
for(int j=1;j<=n;j++)
{
dist[i][j+n]=sqrt((soldier[0][j]-refuge[0][i])*(soldier[0][j]-refuge[0][i])+(soldier[1][j]-refuge[1][i])*(soldier[1][j]-refuge[1][i]));
dist[j+n][i]=-dist[i][j+n];
c[i][j+n]=1;
}
}
}
void create_graph(double val)
{
//printf("%lf\n",val);
for(int i=sursa;i<=dest;i++)
{
adj[i].clear();
for(int j=sursa;j<=dest;j++) f[i][j]=0;
}
for(int i=1;i<=n;i++)
{
adj[sursa].pb(i);
adj[i].pb(sursa);
adj[dest].pb(i+n);
adj[i+n].pb(dest);
for(int j=1;j<=n;j++)
{
if(dist[i][j+n]<=val)
{
adj[i].pb(j+n);
adj[j+n].pb(i);
}
}
}
}
int bellman()
{
for(int i=sursa;i<=dest;i++)
{
vis[i]=0;
t[i]=-1 ;
d[i]=0x3f3f3f3f;
}
q.push(sursa);
vis[sursa]=1;
d[sursa]=0;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
{
if(c[nod][*it]-f[nod][*it]<=0) continue;
if(d[*it]>d[nod]+dist[nod][*it])
{
d[*it]=d[nod]+dist[nod][*it];
t[*it]=nod;
if(vis[*it]) continue;
vis[*it]=1;
q.push(*it);
}
}
vis[nod]=0;
}
// printf("X");
if(d[dest]==0x3f3f3f3f) return 0;
return 1;
}
int do_flow()
{
int flow=0;
sol=0;
while(bellman())
{
int minim=0x3f3f3f3f;
for(int i=dest;i!=sursa;i=t[i]) minim=min(minim,c[t[i]][i]-f[t[i]][i]);
flow+=minim;
sol+=minim*d[dest];
for(int i=dest;i!=sursa;i=t[i])
{
f[t[i]][i]+=minim;
f[i][t[i]]-=minim;
}
}
return flow;
}
inline void do_bs()
{
int st=0,dr=10000000;
double rasp=0,costperrasp=0;
while(st<=dr)
{
int mij=((st+dr))/2;
create_graph((double)((double)(mij)/10000));
int vrr=do_flow();
// printf("%d %d %d %d\n",st,mij,dr,vrr);
if(vrr==n)
{
rasp=(double)((double)mij)/10000;
costperrasp=sol;
dr=mij-1;
}
else st=mij+1;
}
printf("%lf %lf\n",rasp,costperrasp);
}
int main()
{
freopen ("adapost.in","r",stdin);
freopen ("adapost.out","w",stdout);
citire();
do_bs();
}