Pagini recente » Cod sursa (job #600388) | Cod sursa (job #2053662) | Cod sursa (job #2637927) | Cod sursa (job #2358365) | Cod sursa (job #187118)
Cod sursa(job #187118)
/*
* Complexity: O(N^3 * log N + N^4)
*/
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int MAX_N = 401;
const double INF = 1.e10;
#define point pair <double, double>
#define x first
#define y second
ifstream in("adapost.in");
ofstream out("adapost.out");
int N;
point S[MAX_N], A[MAX_N];
double D[MAX_N][MAX_N];
vector <double> dist;
char cap[2 * MAX_N + 2][2 * MAX_N + 2];
vector <int> G[2 * MAX_N + 2];
bool visited[2 * MAX_N + 2]; int prec[2 * MAX_N + 2];
double cost[2 * MAX_N + 2][2 * MAX_N + 2], c[2 * MAX_N + 2];
bool in_queue[2 * MAX_N + 2];
inline double Distance(const point &A, const point &B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
void read() {
in >> N;
for(int i = 1; i <= N; ++i)
in >> S[i].x >> S[i].y;
for(int i = 1; i <= N; ++i)
in >> A[i].x >> A[i].y;
}
void init() {
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
dist.push_back(D[i][j] = Distance(S[i], A[j]));
sort(dist.begin(), dist.end());
}
void BF() {
for(int i = 1; i < 2 * N + 2; ++i)
visited[i] = false;
visited[0] = true;
prec[0] = -1;
queue <int> Q;
Q.push(0);
while(!Q.empty()) {
int v = Q.front();
Q.pop();
for(vector <int> :: iterator it = G[v].begin(); it != G[v].end(); ++it)
if(cap[v][*it] && !visited[*it]) {
visited[*it] = true, prec[*it] = v, Q.push(*it);
if(*it == 2 * N + 1)
return;
}
}
}
int flux1(double MAX) {
for(int i = 0; i < 2 * N + 2; ++i)
G[i].clear();
for(int i = 1; i <= N; ++i) {
G[0].push_back(i); cap[0][i] = 1;
G[i].push_back(0); cap[i][0] = 0;
}
for(int i = 1; i <= N; ++i)
for(int j = N + 1; j <= 2 * N; ++j)
if(D[i][j - N] <= MAX) {
G[i].push_back(j); cap[i][j] = 1;
G[j].push_back(i); cap[j][i] = 0;
}
for(int i = N + 1; i <= 2 * N; ++i) {
G[i].push_back(2 * N + 1); cap[i][2 * N + 1] = 1;
G[2 * N + 1].push_back(i); cap[2 * N + 1][i] = 0;
}
int flux_maxim = 0;
do {
BF();
if(visited[2 * N + 1]) {
++flux_maxim;
int u = prec[2 * N + 1], v = 2 * N + 1;
while(u != -1) {
cap[u][v]--;
cap[v][u]++;
v = u;
u = prec[u];
}
}
} while(visited[2 * N + 1]);
return flux_maxim;
}
int binary_search(const int &lo, const int &hi) {
if(lo == hi)
return lo;
if(flux1(dist[(lo + hi) / 2]) == N)
return binary_search(lo, (lo + hi) / 2);
else
return binary_search((lo + hi) / 2 + 1, hi);
}
void Bellman_Ford() {
for(int i = 1; i < 2 * N + 2; ++i)
visited[i] = false, c[i] = INF, in_queue[i] = false;
visited[0] = true;
c[0] = 0;
prec[0] = -1;
in_queue[0] = true;
queue <int> Q;
Q.push(0);
while(!Q.empty()) {
int v = Q.front();
Q.pop();
in_queue[v] = false;
visited[v] = true;
for(vector <int> :: iterator it = G[v].begin(); it != G[v].end(); ++it)
if(cap[v][*it] && c[v] + cost[v][*it] < c[*it]) {
c[*it] = c[v] + cost[v][*it];
prec[*it] = v;
if(!in_queue[*it]) {
in_queue[*it] = true;
Q.push(*it);
}
}
}
}
double flux2(double MAX) {
for(int i = 0; i < 2 * N + 2; ++i)
G[i].clear();
for(int i = 1; i <= N; ++i) {
G[0].push_back(i); cap[0][i] = 1; cost[0][i] = 0;
G[i].push_back(0); cap[i][0] = 0; cost[i][0] = 0;
}
for(int i = 1; i <= N; ++i)
for(int j = N + 1; j <= 2 * N; ++j)
if(D[i][j - N] <= MAX) {
G[i].push_back(j); cap[i][j] = 1; cost[i][j] = D[i][j - N];
G[j].push_back(i); cap[j][i] = 0; cost[j][i] = -D[i][j - N];
}
for(int i = N + 1; i <= 2 * N; ++i) {
G[i].push_back(2 * N + 1); cap[i][2 * N + 1] = 1; cost[i][2 * N + 1] = 0;
G[2 * N + 1].push_back(i); cap[2 * N + 1][i] = 0; cost[2 * N + 1][i] = 0;
}
do {
Bellman_Ford();
if(visited[2 * N + 1]) {
int u = prec[2 * N + 1], v = 2 * N + 1;
while(u != -1) {
cap[u][v]--;
cap[v][u]++;
v = u;
u = prec[u];
}
}
} while(visited[2 * N + 1]);
double cost_minim = 0;
for(int i = 1; i <= N; ++i)
for(int j = N + 1; j <= 2 * N; ++j)
if(D[i][j - N] <= MAX && !cap[i][j])
cost_minim += cost[i][j];
return cost_minim;
}
int main() {
read();
init();
double MAX = dist[binary_search(0, dist.size() - 1)];
out << fixed << setprecision(5);
out << MAX << " " << flux2(MAX);
return 0;
}