Pagini recente » Cod sursa (job #2206085) | Cod sursa (job #1398813) | Cod sursa (job #262973) | Cod sursa (job #2736201) | Cod sursa (job #990628)
Cod sursa(job #990628)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define EPS 1e-4
#define Nmax 810
#define pb push_back
int N, Flow[Nmax][Nmax], Cap[Nmax][Nmax], Source, Sink, Father[Nmax], L[Nmax], R[Nmax];
double Cost[Nmax][Nmax], AnsFlow, AnsDist, Dist[Nmax];
double X[Nmax], Y[Nmax], XA[Nmax], YA[Nmax];
vector<int> G[Nmax], GC[Nmax];
bool Used[Nmax], InQueue[Nmax];
bool BellmanFord()
{
for(int i = Source; i <= Sink; ++ i)
Dist[i] = 1.0 * 0x3f3f3f3f, Father[i] = 0;
Dist[Source] = 0;
queue<int> Q;
Q.push(Source);
while(!Q.empty())
{
int Node = Q.front();
Q.pop();
if(Node == Sink) return 1;
InQueue[Node] = 0;
for(vector<int> :: iterator it = G[Node].begin(); it != G[Node].end(); ++ it)
if(Cap[Node][*it] > Flow[Node][*it] && Dist[*it] > Dist[Node] + Cost[Node][*it])
{
Dist[*it] = Dist[Node] + Cost[Node][*it];
Father[*it] = Node;
if(!InQueue[*it])
InQueue[*it] = 1, Q.push(*it);
}
}
return Dist[Sink] != 1.0 * 0x3f3f3f3f;
}
void MinCostMaxFlow()
{
double MaxFlow = 0.0;
while(BellmanFord())
{
int MinFlow = 0x3f3f3f3f;
for(int Node = Sink; Node != Source; Node = Father[Node])
MinFlow = min(MinFlow, Cap[Father[Node]][Node] - Flow[Father[Node]][Node]);
for(int Node = Sink; Node != Source; Node = Father[Node])
{
Flow[Father[Node]][Node] += MinFlow;
Flow[Node][Father[Node]] -= MinFlow;
}
MaxFlow += 1.0 * MinFlow * Dist[Sink];
}
AnsFlow = MaxFlow;
}
int PairUp(int Node)
{
if(Used[Node]) return 0;
Used[Node] = 1;
for(vector<int> :: iterator it = GC[Node].begin(); it != GC[Node].end(); ++ it)
if(!R[*it] || PairUp(R[*it]))
{
L[Node] = *it;
R[*it] = Node;
return 1;
}
return 0;
}
int MaxMatching()
{
int Ans = 0, OK = 1;
while(OK)
{
OK = 0;
memset(Used, 0, sizeof(Used));
for(int i = 1; i <= N; ++ i)
if(!L[i] && PairUp(i))
Ans ++, OK = 1;
}
return Ans;
}
double Distance(int i, int j)
{
return sqrt((X[i] - XA[j]) * (X[i] - XA[j]) + (Y[i] - YA[j]) * (Y[i] - YA[j]));
}
void BuildGraph(double MaxDist)
{
for(int i = Source; i <= Sink; ++ i)
{
G[i].clear();
GC[i].clear();
L[i] = R[i] = Dist[i] = 0;
}
for(int i = Source; i <= Sink; ++ i)
for(int j = Source; j <= Sink; ++ j)
Cap[i][j] = Flow[i][j] = Cost[i][j] = 0;
Source = 0;
Sink = 2 * N + 1;
for(int i = 1; i <= N; ++ i)
for(int j = 1; j <= N; ++ j)
if(Distance(i, j) <= MaxDist)
{
G[i].pb(j + N);
G[j + N].pb(i);
GC[i].pb(j);
Cap[i][j + N] = 1;
Cost[i][j + N] = Distance(i, j);
Cost[j + N][i] = -Cost[i][j + N];
}
for(int i = 1; i <= N; ++ i)
{
Cap[Source][i] = 1;
Cap[i + N][Sink] = 1;
G[Source].pb(i); G[i].pb(Source);
G[i + N].pb(Sink); G[Sink].pb(i + N);
}
}
int main()
{
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%i", &N);
for(int i = 1; i <= N; ++ i)
scanf("%lf %lf", &X[i], &Y[i]);
for(int i = 1; i <= N; ++ i)
scanf("%lf %lf", &XA[i], &YA[i]);
double Left = 0.0, Right = 0.0, Mid;
for(int i = 1; i <= N; ++ i)
for(int j = 1; j <= N; ++ j)
Right = max(Right, Distance(i, j));
Right += EPS;
int Steps = 0;
while(Steps <= 20)
{
Mid = (Left + Right) / 2;
BuildGraph(Mid);
int Matching = MaxMatching();
if(Matching < N) Left = Mid;
else
{
AnsDist = Mid;
MinCostMaxFlow();
Right = Mid;
}
Steps ++;
}
printf("%f %f\n", AnsDist, AnsFlow);
return 0;
}