Pagini recente » Cod sursa (job #918435) | Cod sursa (job #446919) | Monitorul de evaluare | Cod sursa (job #1571894) | Cod sursa (job #2061264)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("adapost.in");
ofstream fout ("adapost.out");
typedef long long ll;
const int Nmax = 808;
const double eps = 1e-7;
int i, n;
ll st, dr, mid;
double X, Y;
struct point
{
int x, y;
} a[Nmax], b[Nmax];
ll dist(point a, point b)
{
return (ll) (a.x - b.x) * (a.x - b.x) + (ll) (a.y - b.y) * (a.y - b.y);
}
class GreatGraph
{
vector<int> v[Nmax];
bool used[Nmax];
double cost[Nmax][Nmax], d[Nmax];
int cap[Nmax][Nmax], t[Nmax], L[Nmax], R[Nmax];
void add_edge(int x, int y, double cc)
{
v[x].push_back(y);
v[y].push_back(x);
cost[x][y] = cc;
cost[y][x] = -cc;
cap[x][y] = 1;
cap[y][x] = 0;
}
bool bellman()
{
queue<int> q;
memset(t, -1, sizeof(t));
memset(used, 0, sizeof(used));
for(int i=1; i<=2*n+1; ++i) d[i] = 1e9;
d[0] = 0;
t[0] = 1;
q.push(0);
used[0] = 1;
while(!q.empty())
{
int node = q.front();
q.pop();
used[node] = 0;
for(auto it : v[node])
if(cap[node][it] && d[it] > -eps + d[node] + cost[node][it])
{
d[it] = d[node] + cost[node][it];
t[it] = node;
if(!used[it])
{
used[it] = 1;
q.push(it);
}
}
}
if(d[2*n+1] != 1e9) return 1;
return 0;
}
bool cupleaza(int node)
{
used[node] = 1;
for(auto it : v[node])
if(!R[it])
{
L[node] = it;
R[it] = node;
return 1;
}
for(auto it : v[node])
if(!used[R[it]] && cupleaza(R[it]))
{
L[node] = it;
R[it] = node;
return 1;
}
return 0;
}
public:
bool check(ll lim)
{
int i, j;
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
if(dist(a[i], b[j]) <= lim)
v[i].push_back(j);
bool done = 1;
while(done)
{
done = 0;
memset(used, 0, sizeof(used));
for(i=1; i<=n; ++i)
if(!L[i] && !used[i])
done |= cupleaza(i);
}
int cnt = 0;
for(i=1; i<=n; ++i)
{
v[i].clear();
if(L[i]) ++cnt;
}
return (cnt == n);
}
double max_flow_min_cost(int lim)
{
int i, j;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
if(dist(a[i], b[j]) <= lim)
add_edge(i, n+j, sqrt(dist(a[i], b[j])));
for(i=1; i<=n; ++i) add_edge(0, i, 0);
for(i=n+1; i<=2*n; ++i) add_edge(i, 2*n+1, 0);
int node, dad;
double Cost = 0;
while(bellman())
{
node = 2 * n + 1;
while(node)
{
dad = t[node];
cap[dad][node] --;
cap[node][dad] ++;
Cost += cost[dad][node];
node = dad;
}
}
return Cost;
}
} graph;
int main()
{
fin >> n;
for(i=1; i<=n; ++i)
{
fin >> X >> Y;
a[i].x = (int)(X * 1000);
a[i].y = (int)(Y * 1000);
}
for(i=1; i<=n; ++i)
{
fin >> X >> Y;
b[i].x = (int)(X * 1000);
b[i].y = (int)(Y * 1000);
}
st = 0; dr = 2e12;
while(st <= dr)
{
mid = (st + dr) / 2;
if(graph.check(mid)) dr = mid - 1;
else st = mid + 1;
}
fout << setprecision(5) << fixed;
fout << sqrt(st) / 1000 << ' ';
fout << graph.max_flow_min_cost(st) / 1000 << '\n';
return 0;
}