Pagini recente » Cod sursa (job #1760845) | Cod sursa (job #2274600) | Cod sursa (job #1998254) | Cod sursa (job #3136040) | Cod sursa (job #1936768)
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#define pb push_back
using namespace std;
const int nmax=802;
int n;
int adj[nmax][nmax];
double vals[nmax*nmax];
int sursa,dest,c[nmax][nmax],f[nmax][nmax],t[nmax],vis[nmax],l[nmax],r[nmax];
double soldier[2][nmax],refuge[2][nmax],dist[nmax][nmax],d[nmax];
int q[nmax*100];
inline void citire()
{
scanf("%d",&n);
dest=2*n+1;
int ps=0;
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];
vals[ps]=dist[i][j+n];
++ps;
c[i][j+n]=1;
}
}
sort(vals,vals+ps);
}
inline void create_graph(double val)
{
//printf("%lf\n",val);
for(int i=1;i<=n;i++)
{
adj[sursa][++adj[sursa][0]]=i;
adj[i][++adj[i][0]]=sursa;
adj[dest][++adj[dest][0]]=i+n;
adj[i+n][++adj[i+n][0]]=dest;
for(int j=1;j<=n;j++)
{
if(dist[i][j+n]<=val)
{
adj[i][++adj[i][0]]=j+n;
adj[j+n][++adj[j+n][0]]=i;
}
}
}
}
int bellman()
{
for(int i=sursa;i<=dest;i++)
{
vis[i]=0;
d[i]=0x3f3f3f3f;
}
q[0]=1;
q[1]=sursa;
vis[sursa]=1;
d[sursa]=0;
for(int i=1;i<=q[0];i++)
{
int nod=q[i];
for(int j=1;j<=adj[nod][0];++j)
{
if(c[nod][adj[nod][j]]-f[nod][adj[nod][j]]<=0) continue;
if(d[adj[nod][j]]>d[nod]+dist[nod][adj[nod][j]])
{
d[adj[nod][j]]=d[nod]+dist[nod][adj[nod][j]];
t[adj[nod][j]]=nod;
if(vis[adj[nod][j]]) continue;
vis[adj[nod][j]]=1;
q[++q[0]]=adj[nod][j];
}
}
vis[nod]=0;
}
if(d[dest]==0x3f3f3f3f) return 0;
return 1;
}
double do_flow()
{
double 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]);
sol+=minim*d[dest];
for(int i=dest;i!=sursa;i=t[i])
{
f[t[i]][i]+=minim;
f[i][t[i]]-=minim;
}
}
return sol;
}
int pairup(int nod,double x)
{
if(vis[nod]) return 0;
vis[nod]=1;
for(int j=1;j<=n;j++)
{
if(dist[nod][j+n]<=x&&(r[j]==0))
{
l[nod]=j;
r[j]=nod;
return 1;
}
}
for(int j=1;j<=n;j++)
{
if(dist[nod][j+n]<=x&&(pairup(r[j],x)))
{
l[nod]=j;
r[j]=nod;
return 1;
}
}
return 0;
}
int do_flow2(double x)
{
for(int i=1;i<=n;i++) l[i]=0,r[i]=0;
for(int c=1;c!=0;)
{
c=0;
for(int i=1;i<=n;i++)
{
if(l[i]==0) c|=pairup(i,x);
}
for(int i=1;i<=n;i++) vis[i]=0;
}
int sum=0;
for(int i=1;i<=n;i++) if(l[i]!=0) ++sum;
return sum;
}
inline void do_bs()
{
int dr=n*n -1;
int step=1;
while((step<<1)<=dr) step<<=1;
int rasp=0;
for(;step>=1;step>>=1)
{
if(rasp+step<=dr)
{
int vrr=do_flow2(vals[rasp+step-1]);
if(vrr<n) rasp+=step;
}
}
create_graph(vals[rasp]);
printf("%lf %lf\n",vals[rasp],do_flow());
}
int main()
{
freopen ("adapost.in","r",stdin);
freopen ("adapost.out","w",stdout);
citire();
do_bs();
}