Pagini recente » Cod sursa (job #3231147) | Cod sursa (job #598209) | Cod sursa (job #2668195) | Borderou de evaluare (job #2012394) | Cod sursa (job #1015395)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<double, double> Soldier, Shelter;
class SimpleGraph {
public:
SimpleGraph(int size):
size_(size),
edges_(size) {
}
void addEdge(int from, int to) {
edges_[from].push_back(to);
}
bool didInvertChain(int from, int to) {
queue<int> Q;
Q.push(from);
vector<int> parent(size_, -1);
parent[from] = from;
while (!Q.empty()) {
int node = Q.front();
Q.pop();
if (node == to)
break;
for (auto &next : edges_[node])
if (parent[next] == -1) {
parent[next] = node;
Q.push(next);
}
}
if (parent[to] == -1)
return false;
for (int node = to; node != from; node = parent[node]) {
vector<int> &where = edges_[parent[node]];
where.erase(find(where.begin(), where.end(), node));
edges_[node].push_back(parent[node]);
}
return true;
}
private:
int size_;
vector< vector<int> > edges_;
};
int main() {
ifstream cin("adapost.in");
ofstream cout("adapost.out");
int N; cin >> N;
vector<Soldier> A(N);
vector<Shelter> B(N);
for (int i = 0; i < N; ++i)
cin >> A[i].first >> A[i].second;
for (int i = 0; i < N; ++i)
cin >> B[i].first >> B[i].second;
vector< vector<double> > distance(N, vector<double>(N, 0));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
distance[i][j] = sqrt((A[i].first - B[j].first) * (A[i].first - B[j].first) +
(A[i].second - B[j].second) * (A[i].second - B[j].second));
vector< pair<int, int> > pairs(N * N);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
pairs[i * N + j] = {i, j};
sort(pairs.begin(), pairs.end(), [&](pair<int, int> A, pair<int, int> B) {
return distance[A.first][A.second] < distance[B.first][B.second];
});
SimpleGraph G(2 * N + 2);
for (int i = 0; i < N; ++i) {
G.addEdge(2 * N, i); // source to soldier
G.addEdge(i + N, 2 * N + 1); // shelter to sink
}
int matches = 0;
double maxDistance = 0;
for (auto &pair: pairs) {
G.addEdge(pair.first, pair.second + N);
while (G.didInvertChain(2 * N, 2 * N + 1)) // we invert a chain between the source and sink
// at most one new chain can appear when we add an edge
++matches;
if (matches == N) {
maxDistance = distance[pair.first][pair.second];
break;
}
}
cout.setf(ios::fixed, ios::floatfield);
cout.precision(5);
cout << maxDistance << " ";
cout << 1 << "\n";
}