Pagini recente » Cod sursa (job #193492) | Cod sursa (job #663856) | Cod sursa (job #2013215) | Cod sursa (job #447652) | Cod sursa (job #978088)
Cod sursa(job #978088)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#define ff first
#define ss second
#define newn a[x][i]
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int N = 410;
const int M = 820;
const int s = 0, d = 815;
const int oo = 5000;
typedef pair <double, double> nod;
vector <nod> sold;
vector <int> a[M];
vector <bool> uz(M);
int n, f[M][M], c[M][M], t[M];
double cst[M][M], dist[M], cmin;
queue <int> q;
void Read()
{
fin>>n;
for(int i=1; i<=n; i++)
{
double x, y;
fin>>x>>y;
c[s][i] = 1;
a[s].push_back(i);
sold.push_back(nod(x, y));
}
for(int i=1; i<=n; i++)
{
double x, y; int vf = i + n;
fin>>x>>y;
c[vf][d] = 1;
a[vf].push_back(d);
for(int j=0; j<n; j++)
{
c[j+1][vf] = 1;
a[j+1].push_back(vf);
a[vf].push_back(j+1);
double difx = x - sold[j].ff, dify = y - sold[j].ss;
double cost = sqrt(difx*difx + dify*dify);
cst[j+1][vf] = cost;
cst[vf][j+1] = -cost;
}
}
}
inline bool Bellman_Ford(const double val)
{
int m = 2*n+1;
for(int i=1; i<=m; i++) dist[i] = oo;
dist[d] = oo;
uz.assign(n*2+1, 0);
q.push(s); uz[s] = 1; dist[s] = 0;
while(!q.empty())
{
int x = q.front(); q.pop(); uz[x] = 0;
for(unsigned i=0; i<a[x].size(); i++)
if(f[x][newn] < c[x][newn] && val >= cst[x][newn])
if(dist[x] + cst[x][newn] < dist[newn])
{
t[newn] = x;
dist[newn] = dist[x] + cst[x][newn];
if(!uz[newn]) uz[newn] = 1, q.push(newn);
}
}
return (dist[d] != oo);
}
inline bool OK(const double val)
{
int flux = 0, m = 2*n+2; cmin = 0;
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++)
f[i][j] = 0;
while(Bellman_Ford(val))
{
for(int j=d; j!=s; j=t[j])
f[t[j]][j]++, f[j][t[j]]--;
flux++;
cmin += dist[d];
}
return (flux == n);
}
int main()
{
Read();
double st = 0, dr = 2000, mid;
while(dr - st > 0.00001)
{
mid = (dr+st) / 2;
if(OK(mid)) dr = mid;
else st = mid;
}
fout<<fixed<<setprecision(5)<<dr<<' '<<cmin;
return 0;
}