Pagini recente » Cod sursa (job #1931622) | Cod sursa (job #2651322) | Cod sursa (job #2522772) | Cod sursa (job #2326034) | Cod sursa (job #574486)
Cod sursa(job #574486)
# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <cmath>
# include <cassert>
# define INF 2000000000.
# define DIM 403
# define EPS 0.001
# define pb push_back
# define mp make_pair
# define fs first
# define sc second
using namespace std;
int n, N, c[2*DIM][2*DIM], t[2*DIM], v[2*DIM], a[2*DIM];
double b[2*DIM][2*DIM], d[2*DIM], dst[DIM*DIM], dist=INF, sum=INF;
vector< pair<double,double> >S, A;
queue<int>Q;
void read ()
{
ifstream fin ("adapost.in");
fin>>n;
N=2*n+1;
double a, b;
for(int i=1;i<=n;++i)
{
fin>>a>>b;
S.pb(mp(a,b));
}
for(int i=1;i<=n;++i)
{
fin>>a>>b;
A.pb(mp(a,b));
}
}
double dstnt (int i, int j)
{
double x1, x2, y1, y2;
x1=S[i].fs;
x2=A[j].fs;
y1=S[i].sc;
y2=A[j].sc;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int g (double D)
{
while (Q.size())Q.pop();
for(int i=0;i<=N;++i)
t[i]=-1, v[i]=0;
v[0]=1;
Q.push(0);
int i;
while (Q.size())
{
i=Q.front();Q.pop();
for(int j=0;j<=N;++j)
if (!v[j] && c[i][j]>0)
{
t[j]=i;
v[j]=1;
Q.push(j);
if (j==N)return 1;
}
}
return 0;
}
int ok (double D)
{
for(int i=1;i<=n;++i)
{
c[0][i]=1;
c[i][0]=0;
c[n+i][N]=1;
c[N][n+1]=0;
for(int j=n+1;j<N;++j)
{
if (b[i][j]<=D)
c[i][j]=1;
else
c[i][j]=0;
c[j][i]=0;
}
}
int fl=0;
double dd=0;
while (g(D))
{
++fl;
// dd+=d[N];
for(int i=N;t[i]!=-1;i=t[i])
{
--c[t[i]][i];
++c[i][t[i]];
}
}
if (fl>=n)
{
if (D<dist)
dist=D, sum=dd;
return 1;
}
return 0;
}
void cauta (int st, int dr)
{
if (st==dr)
{
if (dst[st]<dist)
ok(dst[st]);
return;
}
int mij=(st+dr)/2;
if (ok(dst[mij]))
cauta (st, mij);
else
cauta (mij+1, dr);
}
int main()
{
read ();
double d;
int q=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
d=dstnt(i,j);
dst[++q]=d;
b[i][n+j]=d;
b[n+j][i]=-d;
}
sort(dst+1, dst+n*n+1);
cauta (1, n*n);
freopen("adapost.out", "w", stdout);
printf("%lf %.3lf", dist, sum);
return 0;
}