Pagini recente » Cod sursa (job #2529191) | Cod sursa (job #1908840) | Cod sursa (job #518272) | Cod sursa (job #271980) | Cod sursa (job #574581)
Cod sursa(job #574581)
#include<fstream>
#include<iostream>
#include<queue>
#include<cmath>
#define DIM 413
#define INF 2147000000
using namespace std;
struct point{
long long x,y;};
point ad[DIM],v[DIM];
int c[2*DIM][2*DIM],d[DIM][DIM],t[2*DIM],viz[2*DIM],f[2*DIM][2*DIM],n,minim=INF;
queue<int>Q;
int bfs();
void solve(int st,int dr);
int dist(point a,point b);
int verifica(int val);
int main()
{
ifstream fin("adapost.in");
freopen("adapost.out","w",stdout);
fin>>n;
int i,j;
double a,b;
for(i=1;i<=n;i++)
fin>>a>>b,v[i].x=10000*a,v[i].y=10000*b;
for(i=1;i<=n;i++)
fin>>a>>b,ad[i].x=10000*a,ad[i].y=10000*b;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=dist(v[i],ad[j]);
solve(1,2000000000);
a=minim/10000.;
printf("%.3lf 0",a);
return 0;
}
int dist(point a,point b)
{
return sqrt((long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y));
}
void solve(int st,int dr)
{
if(st==dr)
{
if(verifica(st)==1 && st<minim)
minim=st;
return ;
}
int mij=(st+dr)/2;
if(verifica(mij)==1)
{
if(mij<minim)
minim=mij;
solve(st,mij);
}
else
solve(mij+1,dr);
}
int verifica(int val)
{
int i,j,rez=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
c[i][j+n]=0;
f[i][j+n]=0,f[j+n][1]=0;
if(d[i][j]<=val)
c[i][j+n]=1;
}
for(i=1;i<=n;i++)
c[0][i]=1,c[i+n][2*n+1]=1,f[0][i]=0,f[i][0]=0,f[i+n][2*n+1]=f[2*n+1][i+n]=0;
while(bfs()==1)
{
rez++;
for(i=2*n+1;t[i]>=0;i=t[i])
f[t[i]][i]++,
f[i][t[i]]--;
}
if(rez==n)
return 1;
else
return 0;
}
int bfs()
{
while(Q.size())
Q.pop();
Q.push(0);
int i;
for(i=1;i<=2*n+1;i++)
t[i]=-1,viz[i]=0;
t[0]=-1;
viz[0]=1;
while(Q.size())
{
int k=Q.front();
Q.pop();
for(i=1;i<=2*n+1;i++)
if(viz[i]==0 && c[k][i]>f[k][i])
{
viz[i]=1;
t[i]=k;
Q.push(i);
if(i==2*n+1)
return 1;
}
}
return 0;
}