Pagini recente » Cod sursa (job #669265) | Cod sursa (job #1627745) | Cod sursa (job #1347528) | Cod sursa (job #2117941) | Cod sursa (job #2916976)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
struct point{
double x, y;
};
const int N = 400, inf = 1e9;
const double EPS = 1e-8;
point soldat[N + 1], adapost[N + 1];
double calcDist(point a, point b){
return sqrt((abs(a.x - b.x) * abs(a.x - b.x)) + (abs(a.y - b.y) * abs(a.y - b.y)));
}
int n;
int f[2 * N + 1][2 * N + 1], from[2 * N + 1];
double dist[2 * N + 1], cdist[2 * N + 1], aux[2 * N + 1], cost[2 * N + 1][2 * N + 1];
vector <int> adj[2 * N + 1];
void BF(){
for(int i = 0; i <= 2 * n + 1; i++)
aux[i] = inf;
queue <int> Q;
Q.push(0), aux[0] = 0;
while(!Q.empty()){
int nod = Q.front();
Q.pop();
for(auto vec : adj[nod])
if(aux[nod] + cost[nod][vec] < aux[vec] && f[nod][vec] > 0)
aux[vec] = aux[nod] + cost[nod][vec], Q.push(vec);
}
}
priority_queue <pair <double, int>, vector <pair <double, int>>, greater <pair <double, int>>> pq;
bool DJK(){
for(int i = 0; i <= 2 * n + 1; i++)
dist[i] = cdist[i] = inf;
pq.push({0, 0});
dist[0] = cdist[0] = 0;
while(!pq.empty()){
int nod = pq.top().second;
double val = pq.top().first;
pq.pop();
if(val == dist[nod])
for(auto vec : adj[nod])
if(f[nod][vec] > 0 && dist[nod] + cost[nod][vec] + aux[nod] - aux[vec] < dist[vec]){
dist[vec] = dist[nod] + cost[nod][vec] + aux[nod] - aux[vec];
cdist[vec] = cdist[nod] + cost[nod][vec];
pq.push({dist[vec], vec}), from[vec] = nod;
}
}
return(dist[2 * n + 1] != inf);
}
int maxMatch;
double minCost;
void cmcm(double lim){
maxMatch = 0, minCost = 0;
for(int i = 0; i <= 2 * n + 1; i++){
adj[i].clear();
dist[i] = cdist[i] = aux[i] = 0;
from[i] = 0;
}
for(int i = 1; i <= n; i++){
adj[0].push_back(i), adj[i + n].push_back(2 * n + 1);
f[0][i] = 1, f[i + n][2 * n + 1] = 1;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(cost[i][j + n] <= lim){
adj[i].push_back(j + n), adj[j + n].push_back(i);
f[i][j + n] = inf;
}
BF();
while(DJK()){
int nod = 2 * n + 1, flow = inf;
while(nod != 0)
flow = min(flow, f[from[nod]][nod]), nod = from[nod];
nod = 2 * n + 1, maxMatch += flow;
while(nod != 0)
f[from[nod]][nod] -= flow, f[nod][from[nod]] += flow, nod = from[nod];
minCost += flow * cdist[2 * n + 1];
for(int i = 0; i <= 2 * n + 1; i++)
aux[i] = dist[i];
}
}
int main(){
fin >> n;
for(int i = 1; i <= n; i++)
fin >> soldat[i].x >> soldat[i].y;
for(int i = 1; i <= n; i++)
fin >> adapost[i].x >> adapost[i].y;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
cost[i][j + n] = calcDist(soldat[i], adapost[j]);
cost[j + n][i] = -cost[i][j];
}
double st = 0, dr = 2000;
pair <double, double> ans = {0, 0};
while(dr - st > EPS){
double mij = (st + dr) / 2;
cmcm(mij);
if(maxMatch == n)
ans = {mij, minCost}, dr = mij;
else
st = mij;
}
fout << ans.first << ' ' << ans.second << '\n';
return 0;
}