Pagini recente » Cod sursa (job #2729146) | Cod sursa (job #1802758) | Cod sursa (job #3292630) | Cod sursa (job #1537367) | Cod sursa (job #1519001)
#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];
double capacity[2 * DIM][2 * DIM], cost[2 * DIM][2 * DIM], flux[2 * DIM][2 * DIM];
int parent[2 * DIM];
double d[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 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();
int add = n;
if(node == 0 || (node > n && node < destination))
add = 0;
for (int i = 1; i <= n; i++) {
int child = i + add;
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;
Q.push(child);
}
}
if(!add && node != source){
int child = destination;
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;
Q.push(child);
}
}
else if (add && node != destination){
int child = source;
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;
Q.push(child);
}
}
}
return (d[destination] != INF);
}
bool verif(double dist) {
source = 0, destination = 2 * n + 1;
memset(flux, 0, sizeof flux);
memset(cost, 0, sizeof cost);
memset(capacity, 0, sizeof capacity);
solution = 0;
for (int i = 1; i <= n; i++) {
capacity[source][i] = 1;
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) {
capacity[i][j + n] = 1;
cost[i][j + n] = Distance(i, j);
cost[j + n][i] = -Distance(i, j);
}
}
}
int maxflow = 0;
while (BF()) {
int var = parent[destination];
if (capacity[var][destination] <= flux[var][destination])
continue;
double 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;
maxflow += minim;
}
return(maxflow == n);
}
void binarySearch() {
double left = 0, right = 1500;
while(left <= right) {
double middle = (left + right) / 2;
if(verif(middle))
right = middle - 0.00001;
else
left = middle + 0.00001;
}
verif(left);
fout << setprecision(6) << fixed;
fout << left << " " << 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!