Pagini recente » Cod sursa (job #623163) | Cod sursa (job #2196310) | Cod sursa (job #2498125) | Cod sursa (job #1516354) | Cod sursa (job #1015782)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX = 402;
const double eps = 0.0001;
double inf = 1.0*int(1e9);
int n;
double ww[NMAX][NMAX];
double w[NMAX][NMAX], ax[NMAX], ay[NMAX];
double x[2][NMAX], y[2][NMAX];
bool vx[NMAX], vy[NMAX];
int mch[NMAX];
double maxDist, distSum;
vector< double > distances;
inline double dist(double x1,double y1,double x2,double y2) {
return sqrt( (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
bool dfs(int x){
vx[x] = 1;
for(int y = 0; y < n; y++){
int t = ax[x] + ay[y] - w[x][y];
if(!vy[y] && t == 0){
vy[y] = 1;
if(mch[y] < 0 || dfs(mch[y])) {
mch[y] = x;
return 1;
}
}
}
return 0;
}
bool khun(const int &index){
double upperBound = distances[index] + eps;
for(int i = 0;i < n;i++) {
ax[i] = 0.0;
ay[i] = 0.0;
vx[i] = vy[i] = false;
mch[i] = -1;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
w[i][j] = ww[i][j] < upperBound ? -ww[i][j] : -inf;
ax[i] = max(ax[i], w[i][j]);
}
}
for(int i = 0; i < n; i++){
while(!dfs(i)){
double d = inf;
for(int j = 0; j < n; j++) {
if(!vy[j]) {
for(int k = 0; k < n; k++) {
if(vx[k]) {
d = min(d, ax[k] + ay[j] - w[k][j]);
}
}
}
}
for(int j = 0; j < n; j++) {
if(vx[j]) ax[j] -= d, vx[j] = 0;
if(vy[j]) ay[j] += d, vy[j] = 0;
}
}
}
double currentSum = 0.0;
for(int i = 0;i < n;i++) {
if(w[mch[i]][i] == -inf) {
return false;
}
currentSum += ww[mch[i]][i];
}
maxDist = distances[index];
distSum = currentSum;
return true;
}
void readData() {
scanf("%d",&n);
for(int k = 0;k < 2;k++) {
for(int i = 0;i < n;i++) {
scanf("%lf %lf",&x[k][i],&y[k][i]);
}
}
}
void buildGraph() {
distances.resize(n*n);
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
ww[i][j] = dist(x[0][i],y[0][i],x[1][j],y[1][j]);
distances[n*i + j] = ww[i][j];
}
}
sort(distances.begin(),distances.end());
}
void solve() {
maxDist = inf;
int left = 0, right = n*n - 1;
while(left <= right) {
int mid = (left + right)>>1;
if(khun(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
printf("%.5lf %.5lf\n",maxDist,distSum);
}
int main ()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
readData();
buildGraph();
solve();
return 0;
}