Pagini recente » Cod sursa (job #620747) | Cod sursa (job #2088124) | Cod sursa (job #855306) | Istoria paginii utilizator/dianadobrescu | Cod sursa (job #1903170)
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cmath>
#define pid pair<double,double>
#define x first
#define y second
#define Nmax 405
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
double cost[2*Nmax][2*Nmax],distmin[2*Nmax],cuplaj,costcuplaj;
pid sold[Nmax],adap[Nmax];
int n,C[2*Nmax][2*Nmax],source,sink,tata[2*Nmax];
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]=99999999999;
distmin[source]=0;
viz[source]=1;
Q.push(source);
while(Q.size())
{
int nod=Q.front();
Q.pop();
viz[nod]=0;
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]==99999999999) 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;
double maxim=0,costminim=0;
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=1;j<=n;j++)
{
int nr=(i-1)*n+j;
seg[nr]=distanta(i,j);
}
}
sort(seg+1,seg+n*n+1);
int st=1,dr=n*n;
while(st<=dr)
{
int mij=(st+dr)/2;
memset(cost,0,sizeof(cost));
memset(C,0,sizeof(C));
for(i=1;i<=n;i++)
{
H[i].clear();
H[i+n].clear();
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=1;j<=n;j++)
{
double dist=distanta(i,j);
if(dist<=seg[mij])
{
C[i][j+n]=1;
cost[i][j+n]=dist;
cost[j+n][i]=-dist;
H[i].push_back(j+n);
H[j+n].push_back(i);
}
}
}
cuplaj=costcuplaj=0;
while(bellmanford());
if(cuplaj==n)
{
maxim=seg[mij];
costminim=costcuplaj;
dr=mij-1;
}
else st=mij+1;
}
fout<<maxim<<" "<<costminim;
}