Pagini recente » Cod sursa (job #2999013) | Cod sursa (job #440922) | Cod sursa (job #1613855) | Cod sursa (job #818480) | Cod sursa (job #187102)
Cod sursa(job #187102)
/*
* Complexity: O(N^3 * log N)
*/
// TODO verifica corectitudinea complexitatii
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int MAX_N = 401;
#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 cap1[2 * MAX_N + 2][2 * MAX_N + 2];
vector <int> G[2 * MAX_N + 2];
bool visited[2 * MAX_N + 2], prec[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(cap1[v][*it] && !visited[*it]) {
visited[*it] = true, prec[*it] = v, Q.push(*it);
// if(*it == 11)
// out << prec[*it] << endl;
}
}
}
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); cap1[0][i] = 1;
G[i].push_back(0); cap1[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); cap1[i][j] = 1;
G[j].push_back(i); cap1[j][i] = 0;
}
for(int i = N + 1; i <= 2 * N; ++i) {
G[i].push_back(2 * N + 1); cap1[i][2 * N + 1] = 1;
G[2 * N + 1].push_back(i); cap1[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) {
cap1[u][v]--;
cap1[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);
}
int main() {
read();
init();
// out << flux1(10000000) << endl;
out << dist[binary_search(0, dist.size() - 1)] << " ";
return 0;
}