Pagini recente » Cod sursa (job #527045) | Cod sursa (job #538828) | Cod sursa (job #2275880) | Cod sursa (job #2286740) | Cod sursa (job #1519045)
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <cstring>
#define DIM (400 + 5)
#define INF (1 << 30)
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
int n;
int source, destination;
double solution;
pair<double, double> soldiers[DIM], shelters[DIM];
int capacity[2 * DIM][2 * DIM], flux[2 * DIM][2 * DIM];
int parent[2 * DIM];
double d[2 * DIM], cost[2 * DIM][2 * DIM];
vector<int> L[2 * DIM];
double Distance(int x, int y) {
return sqrt((soldiers[x].first - shelters[y].first) * (soldiers[x].first - shelters[y].first) + (soldiers[x].second - shelters[y].second) * (soldiers[x].second - shelters[y].second));
}
bool vis[2 * DIM];
bool BF() {
queue<int> Q;
for (int i = source; i <= destination; i++) {
parent[i] = 0;
d[i] = INF;
}
parent[source] = -1;
d[source] = 0;
Q.push(source);
while (Q.size()) {
int node = Q.front();
Q.pop();
vis[node] = false;
if(node == destination)
continue;
for (int i = 0; i < L[node].size(); i++) {
int child = L[node][i];
double C = cost[node][child];
if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {
d[child] = d[node] + C;
parent[child] = node;
if(!vis[child])
Q.push(child);
vis[child] = true;
}
}
}
return (d[destination] != INF);
}
void maxFlow(double dist) {
source = 0, destination = 2 * n + 1;
memset(vis, false, sizeof vis);
solution = 0;
for (int i = 1; i <= 2 * n; i++)
L[i].clear();
for (int i = 1; i <= n; i++) {
L[source].push_back(i);
L[i].push_back(source);
capacity[source][i] = 1;
L[i + n].push_back(destination);
L[destination].push_back(i + n);
capacity[i + n][destination] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ( Distance(i, j) - dist < 0.000001) {
L[i].push_back(j + n);
L[j + n].push_back(i);
capacity[i][j + n] = 1;
cost[i][j + n] = Distance(i, j);
cost[j + n][i] = -Distance(i, j);
}
}
}
while (BF()) {
int var = parent[destination];
if (capacity[var][destination] <= flux[var][destination])
continue;
int minim = capacity[var][destination] - flux[var][destination];
while (parent[var] != -1){
minim = min(minim, capacity[parent[var]][var] - flux[parent[var]][var]);
var = parent[var];
}
var = parent[destination];
flux[var][destination] += minim;
flux[destination][var] -= minim;
while (parent[var] != -1){
flux[parent[var]][var] += minim;
flux[var][parent[var]] -= minim;
var = parent[var];
}
solution += d[destination] * minim;
}
}
int Right[2 * DIM], Left[2 * DIM];
bool cupleaza(int node) {
vis[node] = true;
for (int i = 0; i < L[node].size(); i++) {
int child = L[node][i];
if(!Right[child]) {
Left[node] = child;
Right[child] = node;
return true;
}
}
for (int i = 0; i < L[node].size(); i++) {
int child = L[node][i];
if(!vis[Right[child]] && cupleaza(Right[child])) {
Left[node] = child;
Right[child] = node;
return true;
}
}
return false;
}
bool verif(double dist) {
memset(Right, 0, sizeof Right);
memset(Left, 0, sizeof Left);
for (int i = 1; i <= 2 * n; i++)
L[i].clear();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if ( Distance(i, j) - dist < 0.000001)
L[i].push_back(j);
bool ok;
int cuplaj = 0;
do {
ok = false;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) {
if(!Left[i] && cupleaza(i)) {
ok = true;
cuplaj++;
}
}
}while (ok);
return (cuplaj == n);
}
void binarySearch() {
double left = 0, right = 1500;
for (int i = 1; i <= 25; i++) {
double middle = (left + right) / 2;
if(verif(middle))
right = middle;
else
left = middle;
}
maxFlow(right);
fout << setprecision(6) << fixed;
fout << right << " " << solution << "\n";
}
int main () {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> soldiers[i].first >> soldiers[i].second;
for (int i = 1; i <= n; i++)
fin >> shelters[i].first >> shelters[i].second;
binarySearch();
return 0;
}
//Miriam e tare!