Pagini recente » Cod sursa (job #2485048) | Cod sursa (job #2014011) | Cod sursa (job #1142930) | Cod sursa (job #2119414) | Cod sursa (job #2632941)
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 800;
const double INF = 2.e9;
struct POINT
{
double x , y;
POINT(double tx = 0.0 , double ty = 0.0)
{
x = tx;
y = ty;
}
};
POINT P[NMAX + 5];
int cf[NMAX + 5][NMAX + 5] , p[NMAX + 5] , n , s , t;
double cst[NMAX + 5][NMAX + 5] , d[NMAX + 5] , mch[80205];
vector <int> G[NMAX + 5];
double dist(POINT P1 , POINT P2)
{
return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}
struct path
{
int nod;
double cost;
path(int x = 0 , double y = 0.0)
{
nod = x;
cost = y;
}
};
bool operator<(const path& a , const path& b)
{
return a.cost > b.cost;
}
int dijkstra()
{
int u , v , i;
double cost , new_cost;
for(i = 0 ; i <= t ; i ++)
d[i] = INF;
d[s] = 0;
priority_queue <path> pq;
pq.push(path(s , 0.0));
while(!pq.empty())
{
u = pq.top().nod;
cost = pq.top().cost;
pq.pop();
if(d[u] < cost)
continue;
for(i = 0 ; i < G[u].size() ; i ++)
{
v = G[u][i];
if(cf[u][v])
{
new_cost = d[u] + cst[u][v];
if(new_cost < d[v])
{
d[v] = new_cost;
p[v] = u;
pq.push(path(v , new_cost));
}
}
}
}
if(d[t] != INF)
return 1;
return 0;
}
int get_flow()
{
int nod , flow;
flow = INT_MAX;
for(nod = t ; nod != s ; nod = p[nod])
flow = min(flow , cf[p[nod]][nod]);
return flow;
}
double set_flow(int flow)
{
for(int nod = t ; nod != s ; nod = p[nod])
{
cf[p[nod]][nod] -= flow;
cf[nod][p[nod]] += flow;
}
return d[t] * flow;
}
void init(double lim)
{
int i , j;
memset(cf , 0 , sizeof(cf));
for(i = 1 ; i <= n ; i ++)
for(j = n + 1 ; j <= 2 * n ; j ++)
if(cst[i][j] <= lim)
cf[i][j] = 1;
for(i = 1 ; i <= n ; i ++)
cf[s][i] = cf[i + n][t] = 1;
}
double fmcm(double lim)
{
int aux , flow = 0;
double cost = 0.0;
init(lim);
while(dijkstra())
{
aux = get_flow();
cost += set_flow(aux);
flow += aux;
}
if(flow == n)
return cost;
return -INF;
}
void bs()
{
int st , dr , med , last;
double aux , sumdist;
st = 1;
dr = n * n;
while(st <= dr)
{
med = (st + dr) / 2;
aux = fmcm(mch[med]);
if(aux >= 0)
{
last = med;
sumdist = aux;
dr = med - 1;
}
else
st = med + 1;
}
printf("%.5lf %.5lf\n" , mch[last] , sumdist);
}
int main()
{
freopen("adapost.in" , "r" , stdin);
freopen("adapost.out" , "w" , stdout);
int i , j , k;
double x , y;
scanf("%d" , &n);
for(i = 1 ; i <= 2 * n ; i ++)
{
scanf("%lf%lf" , &x , &y);
P[i] = POINT(x , y);
}
k = 0;
for(i = 1 ; i <= n ; i ++)
for(j = n + 1 ; j <= 2 * n ; j ++)
{
G[i].push_back(j);
G[j].push_back(i);
mch[++ k] = dist(P[i] , P[j]);
cf[i][j] = 1;
cst[i][j] = mch[k];
cst[j][i] = -mch[k];
}
s = 0;
t = 2 * n + 1;
for(i = 1 ; i <= n ; i ++)
{
G[s].push_back(i);
G[i].push_back(s);
G[i + n].push_back(t);
G[t].push_back(i + n);
cf[s][i] = cf[i + n][t] = 1;
}
sort(mch + 1 , mch + k + 1);
bs();
return 0;
}