Pagini recente » Rating Laura Balan (lauraxxx) | Cod sursa (job #1058875) | Cod sursa (job #2055065) | Cod sursa (job #1799800) | Cod sursa (job #1528943)
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <fstream>
#include <cstring>
#include <queue>
#define inf 1<<30
#define nmax 810
#define eps 0.0001
using namespace std;
struct point{double x;double y;};
point p[nmax];
double r[nmax][nmax],sol;
short c[nmax][nmax],f[nmax][nmax];
int n,st[nmax],dr[nmax];
int dest;
bitset <nmax*2> uz;
vector <int> v[nmax];
queue <int> q;
double dist(const point &a,const point &b)
{
return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cuplaj(int x)
{
int i,y;
uz[x]=1;
for (i=0;i<v[x].size();i++) {
y=v[x][i];
if (dr[y]==0) {
st[x]=y;
dr[y]=x;
return 1;
}
}
for (i=0;i<v[x].size();i++) {
y=v[x][i];
if (uz[dr[y]]=0&&cuplaj(dr[y])) {
st[x]=y;
dr[y]=x;
return 1;
}
}
return 0;
}
int solvesol()
{
int i,ok;
for (i=1;i<=n;i++)
st[i]=0,dr[i]=0;
do
{
ok=0;
uz.reset();
for (i=1;i<=n;i++)
if (st[i]==0&&cuplaj(i))
ok=1;
}while (ok);
for (i=1;i<=n;i++)
if (st[i]==0)
return 0;
return 1;
}
double d[nmax];
int t[nmax];
void make_graph(double mid,int l)
{
int i,j;
for (i=1;i<=n;i++)
v[i].clear();
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++)
if (r[i][j]<=mid) {
v[i].push_back(l==0?j-n:j);
if (l==1) {
v[j].push_back(i);
c[i][j]=1;
}
}
if (l==1) {
for (i=1;i<=n;i++) {
v[0].push_back(i);
v[i].push_back(0);
c[0][i]=1;
}
for (i=n+1;i<=2*n;i++) {
v[i].push_back(dest);
v[dest].push_back(i);
c[i][dest]=1;
}
}
}
double bfs()
{
int x,y,i;
for (i=1;i<=dest;i++)
d[i]=inf;
q.push(0);
uz.reset();
uz[0]=1;
while (!q.empty()) {
x=q.front();
q.pop();
uz[x]=0;
for (i=0;i<v[x].size();i++) {
y=v[x][i];
if (f[x][y]<c[x][y]&&d[y]>d[x]+r[x][y]) {
d[y]=d[x]+r[x][y];
t[y]=x;
if (uz[y]==0) {
d[y]=d[x]+r[x][y];
if (uz[y]==0) {
uz[y]=1;
q.push(y);
}
}
}
}
}
if (d[dest]==inf)
return 0;
int add=inf;
for (i=dest;i;i=t[i])
add=min(add,c[t[i]][i]-f[t[i]][i]);
return add*d[dest];
}
double fmcm()
{
double a=0,b=0;
int i;
while (1) {
a=bfs();
if (a==0)
break;
b+=a;
for (i=dest;i;i=t[i]) {
f[t[i]][i]++;
f[i][t[i]]--;
}
}
return b;
}
int main()
{
ifstream fin("adapost.in");
ofstream fout("adapost.out");
fin>>n;
int i,j;
double kx,ky;
for (i=1;i<=2*n;i++) {
fin>>kx>>ky;
p[i].x=kx;p[i].y=ky;
}
dest=2*n+1;
double st=0,dr=0,mid;
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++) {
r[i][j]=dist(p[i],p[j]);
if (r[i][j]>dr)
dr=r[i][j];
r[j][i]=-r[i][j];
}
while (dr-st>eps) {
mid=(st+dr)/2;
make_graph(mid,0);
if (solvesol()) {
sol=mid;
dr=mid;
}
else
st=mid;
}
make_graph(st,0);
if (solvesol())
sol=st;
make_graph(sol,1);
fout<<setprecision(10)<<fixed<<sol/1.0<<' '<<fmcm()/1.0<<'\n';
return 0;
}