Pagini recente » Cod sursa (job #1904351) | Cod sursa (job #1667362) | Cod sursa (job #1555675) | Cod sursa (job #1704526) | Cod sursa (job #1903220)
#include <bits/stdc++.h>
#define pid pair<double,double>
#define x first
#define y second
#define Nmax 405
#define inf 10000000
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
double cost[2*Nmax][2*Nmax],distmin[2*Nmax],costcuplaj;
pid sold[Nmax],adap[Nmax];
int n,C[2*Nmax][2*Nmax],source,sink,tata[2*Nmax],cuplaj;
queue<int>Q;
vector<int>H[2*Nmax];
vector<int>::iterator it;
bitset<2*Nmax>viz;
double seg[Nmax*Nmax];
double distanta(int i,int j)
{
return sqrt((sold[i].x-adap[j].x)*(sold[i].x-adap[j].x)+(sold[i].y-adap[j].y)*(sold[i].y-adap[j].y));
}
bool bellmanford()
{
viz.reset();
for(int i=1;i<=2*n+1;i++) distmin[i]=inf;
distmin[source]=0;
viz[source]=1;
Q.push(source);
while(Q.size())
{
int nod=Q.front();
Q.pop();
viz[nod]=0;
if(nod==sink) continue;
for(it=H[nod].begin();it!=H[nod].end();it++)
{
if(C[nod][*it] && (distmin[*it]>distmin[nod]+cost[nod][*it]))
{
distmin[*it]=distmin[nod]+cost[nod][*it];
tata[*it]=nod;
if(viz[*it]==0)
{
viz[*it]=1;
Q.push(*it);
}
}
}
}
if(distmin[sink]==inf) return 0;
int fmin=inf;
for(int i=sink;i!=source;i=tata[i])
{
fmin=min(fmin,C[tata[i]][i]);
}
for(int i=sink;i!=source;i=tata[i])
{
C[tata[i]][i]-=fmin;
C[i][tata[i]]+=fmin;
}
cuplaj+=fmin;
costcuplaj+=1.0*fmin*distmin[sink];
return 1;
}
int main()
{
int i,j,nr=0;
double maxim=0,costminim=inf;
fin>>n;
sink=2*n+1;
for(i=1;i<=n;i++) fin>>sold[i].x>>sold[i].y;
for(i=1;i<=n;i++) fin>>adap[i].x>>adap[i].y;
for(i=1;i<=n;i++)
{
for(j=n+1;j<=2*n;j++)
{
seg[++nr]=distanta(i,j-n);
cost[i][j]=seg[nr];
cost[j][i]=-seg[nr];
}
}
sort(seg+1,seg+n*n+1);
int st=1,dr=n*n;
while(st<=dr)
{
int mij=(st+dr)/2;
memset(C,0,sizeof(C));
for(i=0;i<=2*n+5;i++) H[i].clear();
for(i=1;i<=n;i++)
{
C[source][i]=C[i+n][sink]=1;
H[i].push_back(source);
H[source].push_back(i);
H[i+n].push_back(sink);
H[sink].push_back(i+n);
}
for(i=1;i<=n;i++)
{
for(j=n+1;j<=2*n;j++)
{
if(cost[i][j]-seg[mij]< 0.000001)
{
C[i][j]=1;
H[i].push_back(j);
H[j].push_back(i);
}
}
}
cuplaj=costcuplaj=0;
while(bellmanford());
if(cuplaj==n)
{
maxim=seg[mij];
if(costcuplaj<costminim) costminim=costcuplaj;
dr=mij-1;
}
else st=mij+1;
}
fout<<maxim<<" "<<costminim;
}