Pagini recente » Cod sursa (job #575796) | Cod sursa (job #2555457) | Cod sursa (job #2329588) | Cod sursa (job #1399970) | Cod sursa (job #682256)
Cod sursa(job #682256)
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define NMAx 810
#define oo (1<<30)
#define pb push_back
#define dist(a,b,c,d) sqrt((a-b)*(a-b)+(c-d)*(c-d))
using namespace std;
vector <int> G[NMAx];
vector <double> v;
queue <int> Q;
int n,S,D,color,inQ[NMAx],tata[NMAx];
int viz[NMAx],L[NMAx],R[NMAx];
double sol,e,Cost[NMAx][NMAx],dist[NMAx];
double X[NMAx],Y[NMAx];
bool Flux[NMAx][NMAx];
void reset_graph() {
for(int i=1;i<=2*n;i++) {
G[i].clear();
L[i]=R[i]=0;
}
}
bool BF() {
int i,nod,vecin;
for(i=S;i<=D;i++)
dist[i]=oo;
dist[S]=0;
Q.push(S);
color++;
while(!Q.empty()) {
nod=Q.front();
Q.pop();
inQ[nod]=false;
for(i=0;i<G[nod].size();i++) {
vecin=G[nod][i];
if(Flux[nod][vecin]>0&&dist[vecin]>dist[nod]+Cost[nod][vecin]) {
dist[vecin]=dist[nod]+Cost[nod][vecin];
tata[vecin]=nod;
if(inQ[nod]!=color) {
Q.push(vecin);
inQ[vecin]=color;
}
}
}
}
if(dist[D]==oo)
return 0;
return 1;
}
void bulid_flow_network() {
int i,j;
double d;
S=0;
D=2*n+1;
reset_graph();
for(i=1;i<=n;i++) {
G[S].pb(i);
Flux[S][i]=1;
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++) {
d=dist(X[i],X[j],Y[i],Y[j]);
if(d>e)
continue;
G[i].pb(j);
Flux[i][j]=1;
Cost[i][j]=d;
G[j].pb(i);
Cost[j][i]=-d;
}
for(i=n+1;i<=2*n;i++) {
G[i].pb(D);
Flux[i][D]=1;
}
}
bool cuplaj(int nod) {
int i;
if(viz[nod]==color)
return 0;
else
viz[nod]=color;
for(i=0;i<G[nod].size();i++)
if(!L[G[nod][i]]) {
L[G[nod][i]]=nod;
R[nod]=G[nod][i];
return 1;
}
for(i=0;i<G[nod].size();i++)
if(cuplaj(L[G[nod][i]])) {
L[G[nod][i]]=nod;
R[nod]=G[nod][i];
return 1;
}
return 0;
}
int solution(double k) {
int i,j,ok=1,nr=0;
reset_graph();
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(dist(X[i],X[j],Y[i],Y[j])<=k)
G[i].pb(j);
while(ok) {
ok=0;
color++;
for(i=1;i<=n;i++)
if(!R[i]&&cuplaj(i)) {
nr++;
ok=1;
}
}
return nr;
}
int binary_search() {
int i,step;
for(step=1;step<v.size();step<<=1);
for(i=0;step;step>>=1)
if(i+step<v.size()&&solution(v[i+step])<n)
i+=step;
return i+1;
}
void citire() {
ifstream in("adapost.in");
in>>n;
for(int i=1;i<=2*n;i++)
in>>X[i]>>Y[i];
in.close();
}
void afis() {
ofstream out("adapost.out");
out<<fixed<<setprecision(5)<<e<<' ';
out<<fixed<<setprecision(5)<<sol<<'\n';
out.close();
}
int main() {
int i,j,flow,nod;
citire();
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
v.pb(dist(X[i],X[j],Y[i],Y[j]));
sort(v.begin(),v.end());
e=v[binary_search()];
bulid_flow_network();
color=0;
while(BF()) {
flow=oo;
for(nod=D;nod!=S;nod=tata[nod])
flow=min(flow,(int)Flux[tata[nod]][nod]);
for(nod=D;nod!=S;nod=tata[nod]) {
Flux[tata[nod]][nod]-=flow;
Flux[nod][tata[nod]]+=flow;
}
sol+=dist[D];
}
afis();
return 0;
}