Pagini recente » Cod sursa (job #170450) | Cod sursa (job #1698519) | Cod sursa (job #656841) | Cod sursa (job #1531806) | Cod sursa (job #741671)
Cod sursa(job #741671)
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define maxn 405
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
FILE*f=fopen("adapost.in","r");
FILE*g=fopen("adapost.out","w");
int n;
int L[maxn],R[maxn],viz[maxn];
double v[maxn*maxn],lim,Dist[maxn<<1];
int S,D;
int Cp[maxn<<1][maxn<<1],F[maxn<<1][maxn<<1],C[maxn<<1],inQ[maxn<<1],T[maxn<<1];
vector< pair<int,double> >G[maxn];
vector<int>V[maxn<<1]; queue<int>Q;
double cost[maxn<<1][maxn<<1];
struct pct{
double x,y;
}A[maxn],B[maxn];
inline void citire () {
fscanf(f,"%d",&n);
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
}
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%lf %lf",&B[i].x,&B[i].y);
}
}
inline double dist ( const pct &a , const pct &b ){
double d = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
return sqrt(d);
}
bool pairup ( int nod ){
if ( viz[nod] ) return 0;
viz[nod] = 1;
for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
int nodvcn = itt->first; double cost = itt->second;
if ( cost <= lim ){
if ( !R[nodvcn] ){
L[nod] = nodvcn; R[nodvcn] = nod;
return 1;
}
}
}
for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
int nodvcn = itt->first; double cost = itt->second;
if ( cost <= lim ){
if ( pairup(R[nodvcn]) ){
L[nod] = nodvcn; R[nodvcn] = nod;
return 1;
}
}
}
return 0;
}
inline bool cuplaj () {
memset(L,0,sizeof(L)); memset(R,0,sizeof(R));
int ok = 1;
do{
ok = 0; memset(viz,0,sizeof(viz));
for ( int i = 1 ; i <= n ; ++i ){
if ( !L[i] )
ok |= pairup(i);
}
}while(ok);
int cuplaj = 0;
for ( int i = 1 ; i <= n ; ++i ){
if ( L[i] ){
++cuplaj;
}
}
return cuplaj == n;
}
inline void first () {
int index = 0;
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= n ; ++j ){
v[++index] = dist(A[i],B[j]);
G[i].pb(mp(j,v[index]));
}
}
sort(v+1,v+index+1);
int p = 1,m,u = index;
while ( p <= u ){
m = (p + u) >> 1;
lim = v[m];
if ( cuplaj() ){
u = m - 1;
}
else{
p = m + 1;
}
}
lim = v[p];
fprintf(g,"%.5lf ",lim);
}
inline double abs ( const double &j ){
if ( j < 0 )
return -j;
return j;
}
inline bool bellman_ford () {
Q.push(S); inQ[S] = 1;
for ( int i = 1 ; i <= D ; ++i ){
Dist[i] = INF;
}
Dist[S] = 0;
while ( !Q.empty() ){
int nod = Q.front(); Q.pop(); inQ[nod] = 0;
for ( vector<int>::iterator itt = V[nod].begin() ; itt != V[nod].end() ; ++itt ){
int nodvcn = (*itt);
if ( Dist[nodvcn] > Dist[nod] + cost[nod][nodvcn] && F[nod][nodvcn] < Cp[nod][nodvcn] && abs(cost[nod][nodvcn] <= lim) ){
Dist[nodvcn] = Dist[nod] + cost[nod][nodvcn]; T[nodvcn] = nod;
if ( !inQ[nodvcn] ){
Q.push(nodvcn);
inQ[nodvcn] = 1;
}
}
}
}
return Dist[D] != INF;
}
inline void flux () {
double flow_cost = 0;
while ( bellman_ford() ){
int nod;
for ( nod = D ; T[nod] ; nod = T[nod] ){
++F[T[nod]][nod];
--F[nod][T[nod]];
}
flow_cost += Dist[D];
}
fprintf(g,"%.5lf\n",flow_cost);
}
inline void second () {
S = n+n+1; D = n+n+2;
for ( int i = 1 ; i <= n ; ++i ){
V[S].pb(i); V[i].pb(S);
Cp[S][i] = 1;
}
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= n ; ++j ){
int nod = j + n;
cost[i][nod] = dist(A[i],B[j]);
if ( cost[i][nod] <= lim ){
V[i].pb(nod); V[nod].pb(i);
Cp[i][nod] = 1;
cost[nod][i] = -cost[i][nod];
}
}
}
for ( int i = 1 ; i <= n ; ++i ){
int nod = i + n;
V[nod].pb(D);
Cp[nod][D] = 1;
}
flux();
}
int main () {
citire();
first();
second();
fclose(f);
fclose(g);
return 0;
}