Pagini recente » Cod sursa (job #2151194) | Cod sursa (job #657371) | Cod sursa (job #3129993) | Cod sursa (job #2245412) | Cod sursa (job #1397415)
#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
#include <algorithm>
#include <time.h>
#define MAXN 420
#define INF 1e5
#define EPS 1e-6
#define x first
#define y second
using namespace std;
const int off = 405, start = 0, fin = 402;
int n, cap[2 * MAXN][2 * MAXN], fx[2 * MAXN][2 * MAXN], bk[2 * MAXN];
double totcst;
bool cuplat[MAXN];
vector<double> dst;
pair<double, double> pct[MAXN], ad[MAXN];
vector< pair<int, double> > G[2 * MAXN];
double dstb[2 * MAXN];
inline double euclidDist(pair<double, double> a, pair<double, double> b){
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
bool Bellman_Ford(double mx_c){
int i, a;
bool uzq[2 * MAXN];
queue<int> q;
for(i = 0; i <= n + off; i++){
dstb[i] = INF;
bk[i] = -1;
uzq[i] = 0;
}
dstb[start] = 0;
q.push(start); uzq[start] = 1;
while(!q.empty()){
a = q.front(); q.pop();
uzq[a] = 0;
for(auto b: G[a]){
if(fabs(b.second) < mx_c + EPS && fx[a][b.first] < cap[a][b.first] && dstb[a] + b.second < dstb[b.first]){
dstb[b.first] = dstb[a] + b.second;
bk[b.first] = a;
if(!uzq[b.first]){ uzq[b.first] = 1; q.push(b.first); }
}
}
}
return dstb[fin] < INF;
}
bool works(double mx_c){
int totfx = 0, a, i;
totcst = 0;
memset(fx, 0, sizeof(fx));
while(Bellman_Ford(mx_c)){
for(i = off + 1; i <= off + n; i++){
if(dstb[i] != INF && fx[i][fin] < cap[i][fin]){
a = i;
while(bk[a] != -1){
if(fx[bk[a]][a] == cap[bk[a]][a])
break;
a = bk[a];
}
if(bk[a] != -1)
continue;
totfx++;
totcst += dstb[i];
fx[i][fin]++;
fx[fin][i]--;
a = i;
while(bk[a] != -1){
fx[bk[a]][a]++;
fx[a][bk[a]]--;
a = bk[a];
}
}
}
/*a = fin;
while(bk[a] != -1){
fx[bk[a]][a]++;
fx[a][bk[a]]--;
a = bk[a];
}*/
}
return (totfx == n);
}
int main(){
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j, a;
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%lf %lf", &pct[i].x, &pct[i].y);
for(i = 1; i <= n; i++)
scanf("%lf %lf", &ad[i].x, &ad[i].y);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++){
dst.push_back(euclidDist(pct[i], ad[j]));
G[i].push_back(make_pair(j + off, dst.back()));
G[j + off].push_back(make_pair(i, -dst.back()));
cap[i][j + off] = 1;
}
srand(time(NULL));
double mxcupl = INF;
for(int iter = 1; iter <= 10; iter++){
double mx = 0;
memset(cuplat, 0, sizeof(cuplat));
for(i = 1; i <= n / 2; i++){
a = rand() % n + 1;
while(cuplat[a])
a = rand() % n + 1;
cuplat[a] = 1;
double d = euclidDist(pct[i], ad[a]);
if(d > mx) mx = d;
}
for(j = 1; i <= n; i++){
while(cuplat[j]) j++;
double d = euclidDist(pct[i], ad[j++]);
if(d > mx) mx = d;
}
if(mx < mxcupl) mxcupl = INF;
}
sort(dst.begin(), dst.end());
for(i = 1; i <= n; i++){
cap[start][i] = cap[i + off][fin] = 1;
G[start].push_back(make_pair(i, 0));
G[i + off].push_back(make_pair(fin, 0));
}
int l = n - 1, r = dst.size() - 1, mid;
while(dst[r] > mxcupl + EPS) r--;
while(l < r){
mid = (l + r) >> 1;
if(works(dst[mid])) r = mid - 1;
else l = mid + 1;
}
while(!works(dst[r])) r++;
printf("%.7lf %.7lf\n", dst[r], totcst);
return 0;
}