Pagini recente » Cod sursa (job #3194015) | Cod sursa (job #1351648) | Cod sursa (job #2466714) | Cod sursa (job #1001082) | Cod sursa (job #3032938)
#include <fstream>
#define D double
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define esp 1e-3
#include <iomanip>
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,m,st,dr;
const int N=805;
struct pct
{
D x,y;
}v[N],r[N];
vector<int>a[N];
D get_dist(pct A,pct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int flux[N][N];
D d[N][N];
D dist[N];
bool viz[N];
int dad[N];
D ford(int st,int dr,D MIJ)
{
for(int i=st;i<=dr;i++)
{
dist[i]=1e9;
dad[i]=0;
viz[i]=false;
}
queue<int>q;
dist[st]=0;
q.push(st);
viz[st]=true;
while(!q.empty())
{
int nod=q.front();
q.pop();
viz[nod]=false;
for(auto x: a[nod])
{
if(d[nod][x]<=MIJ&&dist[x]>dist[nod]+d[nod][x]&&flux[nod][x]>0)
{
dist[x]=dist[nod]+d[nod][x];
dad[x]=nod;
if(viz[x]==false)
{
viz[x]=true;
q.push(x);
}
}
}
}
return dist[dr];
}
D get_flux(D lat)
{
D vall=0;
while(true)
{
D sol=ford(st,dr,lat);
if(sol==1e9)
break;
for(int i=dr;i!=st;i=dad[i])
{
flux[dad[i]][i]--;
flux[i][dad[i]]++;
}
vall=vall+sol;
}
for(int i=1;i<=n;i++)
if(flux[st][i]==1)
return 2e9;
return vall;
}
void reset()
{
for(int i=1;i<=n;i++)
flux[st][i]=1,flux[i][st]=0;
for(int i=1;i<=n;i++)
flux[dr][i+n]=0,flux[i+n][dr]=1;
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
flux[i][j]=1,flux[j][i]=0;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
for(int i=1;i<=n;i++)
f>>r[i].x>>r[i].y;
st=0;
dr=2*n+1;
///muchie st - i, i+n dr
for(int i=1;i<=n;i++)
{
a[st].push_back(i);
a[i+n].push_back(dr);
a[dr].push_back(i+n);
a[i].push_back(st);
flux[st][i]=1;
flux[i+n][dr]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
a[i].push_back(j+n);
a[j+n].push_back(i);
flux[i][j+n]=1;
D dd=get_dist(v[i],r[j]);
d[i][j+n]=dd;
d[j+n][i]=-dd;
}
D st=0,dr=4000;
D RE;
while(dr-st>esp)
{
reset();
D mj=(st+dr)/2;
D soll=get_flux(mj);
if(soll<1e9)
RE=soll,dr=mj;
else
st=mj;
}
g<<fixed<<setprecision(6)<<dr<<" ";
g<<fixed<<setprecision(6)<<RE;
return 0;
}