Pagini recente » Cod sursa (job #1672735) | Cod sursa (job #1338947) | Cod sursa (job #631778) | Cod sursa (job #3187835) | Cod sursa (job #3033209)
#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,ANS,st,dr;
const int N=1005;
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];
int niv[N],fr[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(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;
}
return vall;
}
void reset(D mij)
{
for(int i=st; i<=dr; i++)
a[i].clear();
for(int i=1; i<=n; i++)
for(int j=n+1; j<=2*n; j++)
flux[i][j]=0,flux[j][i]=0;
for(int i=1; i<=n; i++)
flux[st][i]=1,flux[i+n][dr]=1;
///adaugam muchiile pana la MIJ
for(int i=1; i<=n; i++)
for(int j=n+1; j<=2*n; j++)
{
if(d[i][j]<=mij)
{
a[i].push_back(j);
a[j].push_back(i);
flux[i][j]=1;
}
}
for(int i=1; i<=n; i++)
{
a[st].push_back(i);
a[i].push_back(st);
a[i+n].push_back(dr);
a[dr].push_back(i+n);
}
}
void bfs(int nod)
{
for(int i=0; i<=dr; i++)
niv[i]=-1,fr[i]=0;
niv[nod]=0;
queue<int>q;
q.push(nod);
while(!q.empty())
{
int next=q.front();
q.pop();
for(auto x : a[next])
if(niv[x]==-1&&flux[next][x]>0)
{
niv[x]=niv[next]+1;
q.push(x);
}
}
}
int dfs(int nod,int mn)
{
if(nod==dr||mn==0)
return mn;
while(fr[nod]<a[nod].size())
{
int x=a[nod][fr[nod]];
fr[nod]++;
if(flux[nod][x]>0&&niv[x]==niv[nod]+1)
{
int R=dfs(x,min(flux[nod][x],mn));
if(R>0)
{
flux[nod][x]-=R;
flux[x][nod]+=R;
return R;
}
}
}
return 0;
}
bool ver()
{
bfs(st);
if(niv[dr]==-1)
return 0;
else
{
int AL=0;
while(true)
{
int x=dfs(st,1e7);
if(x<=0)
break;
else
AL+=x;
}
ANS+=AL;
if(AL==0)
return false;
return true;
}
return false;
}
bool flx(D mij)
{
reset(mij);
ANS=0;
while(ver());
if(ANS==n)
return true;
return false;
}
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++)
for(int j=1; j<=n; j++)
{
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=2000;
D RE;
while(dr-st>esp)
{
D mj=(st+dr)/2;
if(flx(mj))
dr=mj;
else
st=mj;
}
reset(dr);
RE=get_flux(dr);
g<<fixed<<setprecision(6)<<dr<<" ";
g<<fixed<<setprecision(6)<<RE;
return 0;
}