Pagini recente » Cod sursa (job #223095) | Cod sursa (job #2387277) | Cod sursa (job #2670259) | Cod sursa (job #1028894) | Cod sursa (job #1598169)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define N 810
#define INF 1000000.0
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,i,j,x,ok,flux,nr,li,dest,ls,mij,sol,t[N],viz[N],cap[N][N],fl[N][N],st[N],dr[N];
double cost,di[N][N],a[N*N],d[N];
struct punct{double x,y;}p[N],ad[N];
queue<int>q;
vector<pair<int,double> >v[N];
vector<int>gr[N];
inline double dist(punct a,punct b){
return (double)sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
inline bool cupleaza(int x){
if(viz[x])
return 0;
viz[x] = 1;
for(vector<int>::iterator it = gr[x].begin() ; it != gr[x].end() ; ++ it)
if(!st[*it] || cupleaza(st[*it]))
{
st[*it] = x;
dr[x] = *it;
return 1;
}
return 0;
}
inline int cm(){
ok = 1;
int nr = 0;
memset(dr,0,sizeof(dr));
memset(st,0,sizeof(st));
while(ok)
{
memset(viz,0,sizeof(viz));
ok = 0;
for(int i = 1 ; i <= n ; ++ i)
if(!dr[i] && cupleaza(i))
ok = 1 , ++ nr;
}
return nr;
}
inline bool bf(){
for(int i = 1 ; i <= dest ; ++ i)
d[i] = INF;
q.push(0);
viz[0] = 1;
d[0] = 0;
while(!q.empty())
{
x = q.front();
q.pop();
viz[x] = 0;
if(x == dest)
continue;
for(vector<pair<int,double> >::iterator it = v[x].begin() ; it != v[x].end() ; ++ it)
if(d[it->first] > d[x] + it->second && cap[x][it->first])
{
d[it->first] = d[x] + it->second;
t[it->first] = x;
if(!viz[it->first])
{
viz[it->first] = 1;
q.push(it->first);
}
}
}
return d[dest] != INF;
}
inline void fmcm(){
cost = 0;
memset(viz,0,sizeof(viz));
while(bf())
{
x = dest;
while(x)
{
-- cap[t[x]][x];
++ cap[x][t[x]];
x = t[x];
}
cost += d[dest];
}
}
inline void fa_graf(double x){
for(i = 1 ; i <= n ; ++ i)
{
v[0].push_back(make_pair(i , 0));
cap[0][i] = 1;
v[i + n].push_back(make_pair(dest , 0));
cap[i + n][dest] = 1;
for(j = 1 ; j <= n ; ++ j)
if(di[i][j] <= x)
{
v[i].push_back(make_pair(n + j , di[i][j]));
v[n + j].push_back(make_pair(i , -di[i][j]));
cap[i][n + j] = 1;
}
}
}
inline bool verif(double x){
for(i = 1 ; i <= n ; ++ i)
gr[i].clear();
for(i = 1 ; i <= n ; ++ i)
{
for(j = 1 ; j <= n ; ++ j)
if(di[i][j] <= x)
{
gr[i].push_back(j);
}
}
if(cm() == n)
return 1;
return 0;
}
int main()
{
f >> n;
dest = n * 2 + 1;
for(i = 1 ; i <= n ; ++ i)
{
f >> p[i].x >> p[i].y ;
}
for(i = 1 ; i <= n ; ++ i)
{
f >> ad[i].x >> ad[i].y ;
}
for(i = 1 ; i <= n ; ++ i)
for(j = 1 ; j <= n ; ++ j)
di[i][j] = dist(p[i] , ad[j]),
a[++ nr] = di[i][j];
sort(a + 1 , a + nr + 1);
li = 1;
ls = nr;
while(li <= ls)
{
mij = (li + ls)>>1;
if(verif(a[mij]))
{
sol = mij;
ls = mij - 1;
}
else
li = mij + 1;
}
fa_graf(a[sol]);
fmcm();
g << fixed << setprecision(10) << a[sol] << ' ' << cost << '\n';
return 0;
}