Pagini recente » Cod sursa (job #2912160) | Cod sursa (job #968549) | Cod sursa (job #1806314) | Cod sursa (job #488885) | Cod sursa (job #2587316)
#include <iostream>
#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int IINF = 0x3f3f3f3f;
const double DINF = 0x3f3f3f3f3f3f3f3f;
const int N = 410;
const int N2 = N*2;
struct vec2{
double x, y;
};
double sq(double a){
return a*a;
}
double pyt(const vec2 &a, const vec2 &b){
return sqrt(sq(a.x-b.x)+sq(a.y-b.y));
}
int n;
vec2 lt[N], rt[N];
void read(){
fin >> n;
for(int i = 1; i <= n; ++i){
vec2 &a = lt[i];
fin >> a.x >> a.y;
}
for(int i = 1; i <= n; ++i){
vec2 &a = rt[i];
fin >> a.x >> a.y;
}
}
vector<int> gra[N2];
int s, d;
int flo[N2][N2], cap[N2][N2];
double cst[N2][N2];
void bipartize(){
s = 0, d = 2*n+1;
for(int i = 1; i <= n; ++i){
cap[s][i] = cap[i+n][d] = 1;
gra[s].push_back(i);
gra[i+n].push_back(d);
}
for(int a = 1; a <= n; ++a){
for(int b = 1; b <= n; ++b){
cap[a][b+n] = 1;
cst[a][b+n] = pyt(lt[a], rt[b]);
cst[b+n][a] = -cst[a][b+n];
gra[a].push_back(b+n);
gra[b+n].push_back(a);
}
}
}
queue<int> q;
bool inq[N2];
double dist[N2];
int dad[N2];
void bellnuke(){
for(int i = s; i <= d; ++i){
dist[i] = DINF;
}
}
bool bellman(){
bellnuke();
q.push(s);
dist[s] = 0;
while(!q.empty()){
int a = q.front();q.pop();
inq[a] = false;
for(auto b : gra[a]){
double v = dist[a]+cst[a][b];
if(v < dist[b] && flo[a][b] < cap[a][b]){
dist[b] = v;
dad[b] = a;
if(!inq[b]){
q.push(b);
inq[b] = true;
}
}
}
}
return dist[d] < DINF+1;
}
double maxi = 0, total = 0;
void maxflow(){
int fmin = IINF;
for(int x = d; x != s; x = dad[x]){
fmin = min(fmin, cap[dad[x]][x] - flo[dad[x]][x]);
}
for(int x = d; x != s; x = dad[x]){
flo[dad[x]][x] += fmin;
flo[x][dad[x]] -= fmin;
}
total += dist[d];
}
void flowerize(){
while(bellman()){
maxflow();
}
}
void solve(){
bipartize();
flowerize();
}
void write(){
for(int a = 1; a <= n; ++a){
for(int b = 1; b <= n; ++b){
if(flo[a][b+n] == 1){
maxi = max(maxi, cst[a][b+n]);
}
}
}
fout << fixed << setprecision(8);
fout << maxi << " " << total;
}
int main(){
// ios_base::sync_with_stdio(false);
read();
solve();
write();
return 0;
}