Pagini recente » Cod sursa (job #3290961) | Cod sursa (job #3264298) | Cod sursa (job #3285172) | Cod sursa (job #3280548) | Cod sursa (job #3151917)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
vector<int> x[1001];
pair<int, long double> h[1001][1001], h1[1001][1001];
long double v[1001][3], dist[1001], cost;
int n, nr, cuplat[1001], p[1001], prec[1001];
long double Dist(long double a, long double b, long double c, long double d)
{
long double v=sqrt((c-a)*(c-a)+(d-b)*(d-b));
return v;
}
void update(int a)
{while(prec[a]!=-1)
{h[prec[a]][a].first--, cost+=h1[prec[a]][a].second;
h[a][prec[a]].first++, cost-=h1[a][prec[a]].second;
if(a>n && a!=nr)cuplat[a]=1;
a=prec[a];
}
}
struct Data{
int a;
bool operator <(const Data& other) const
{
return dist[a]>dist[other.a];
}
};
bool CM(long double v)
{int a;
cost=0;
for(int i=0;i<=nr;i++)
dist[i]=1e6, p[i]=0;
prec[0]=-1, dist[0]=0;
for(int i=n+1;i<nr;i++)
cuplat[i]=0;
for(int i=0;i<=nr;i++)
for(int j=0;j<=nr;j++)
h[i][j]=h1[i][j];
vector<int>:: iterator I;
queue<int> q;
p[0]=1, q.push(0);
while(q.empty()!=1)
{a=q.front();
p[a]=0;
for(I=x[a].begin();I<x[a].end();I++)
if(h[a][*I].first>0 && dist[*I]>dist[a]+h[a][*I].second && h1[a][*I].second<=v)
{dist[*I]=dist[a]+h[a][*I].second, prec[*I]=a;
if(p[*I]==0)p[*I]=1, q.push(*I);
}
q.pop();
}
if(dist[nr]!=1e6)
{update(nr);
for(int i=0;i<=nr;i++)
for(I=x[i].begin();I<x[i].end();I++)
h[i][*I].second+=dist[i]-dist[*I];
}
priority_queue<Data> q1;
while(dist[nr]!=1e6)
{for(int i=0;i<=nr;i++)
dist[i]=1e6, p[i]=0;
prec[0]=-1, dist[0]=0;
q1.push({0}), p[0]=1;
while(q1.empty()!=1)
{a=q1.top().a;
p[a]=0;
for(I=x[a].begin();I<x[a].end();I++)
if(h[a][*I].first>0 && dist[*I]>dist[a]+h[a][*I].second && h1[a][*I].second<=v)
{dist[*I]=dist[a]+h[a][*I].second, prec[*I]=a;
if(p[*I]==0)p[*I]=1, q1.push({*I});
}
q1.pop();
}
if(dist[nr]!=1e6)
{update(nr);
for(int i=0;i<=nr;i++)
for(I=x[i].begin();I<x[i].end();I++)
h[i][*I].second+=dist[i]-dist[*I];
}
}
bool t=1;
for(int i=1+n;i<nr && t;i++)
if(cuplat[i]==0)t=0;
return t;
}
int main()
{ long double mini=0, sol=0;
fin>>n;
nr=n*2+1;
for(int i=1;i<=n;i++)
{x[0].push_back(i);
x[i].push_back(0);
h1[0][i]={1, 0};
h1[i][0]={0, 0};
}
for(int i=1;i<=n;i++)
{x[nr].push_back(i+n);
x[i+n].push_back(nr);
h1[i+n][nr]={1, 0};
h1[nr][i+n]={0, 0};
}
for(int i=1;i<=n*2;i++)
fin>>v[i][1]>>v[i][2];
for(int i=1;i<=n;i++)
for(int j=n+1;j<nr;j++)
{x[i].push_back(j);
x[j].push_back(i);
h1[i][j]={1, Dist(v[i][1], v[i][2], v[j][1], v[j][2])};
h1[j][i]={0, -Dist(v[i][1], v[i][2], v[j][1], v[j][2])};
}
long double st=0, dr=100000, mij, v;
while(st<=dr)
{mij=(st+dr)/2;
v=CM(mij);
if(v==0)st=mij+0.00001;
else mini=mij, sol=cost, dr=mij-0.00001;
}
fout<<fixed<<setprecision(3)<<mini<<" "<<sol;
return 0;
}