Cod sursa(job #2916976)

Utilizator lolismekAlex Jerpelea lolismek Data 2 august 2022 16:10:29
Problema Adapost Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

struct point{
	double x, y;
};

const int N = 400, inf = 1e9;
const double EPS = 1e-8;
point soldat[N + 1], adapost[N + 1];

double calcDist(point a, point b){
	return sqrt((abs(a.x - b.x) * abs(a.x - b.x)) + (abs(a.y - b.y) * abs(a.y - b.y)));
}

int n;
int f[2 * N + 1][2 * N + 1], from[2 * N + 1];
double dist[2 * N + 1], cdist[2 * N + 1], aux[2 * N + 1], cost[2 * N + 1][2 * N + 1];

vector <int> adj[2 * N + 1];

void BF(){
	for(int i = 0; i <= 2 * n + 1; i++)
		aux[i] = inf;
 
	queue <int> Q;
	Q.push(0), aux[0] = 0;
 
	while(!Q.empty()){
		int nod = Q.front();
		Q.pop();
 
		for(auto vec : adj[nod])                            
			if(aux[nod] + cost[nod][vec] < aux[vec] && f[nod][vec] > 0)
				aux[vec] = aux[nod] + cost[nod][vec], Q.push(vec);
	}
}

	
priority_queue <pair <double, int>, vector <pair <double, int>>, greater <pair <double, int>>> pq;
bool DJK(){
	for(int i = 0; i <= 2 * n + 1; i++)
		dist[i] = cdist[i] = inf;
 
	pq.push({0, 0});
	dist[0] = cdist[0] = 0;
 
	while(!pq.empty()){
		int nod = pq.top().second;
		double val = pq.top().first;
		pq.pop();
 
		if(val == dist[nod])
			for(auto vec : adj[nod])
				if(f[nod][vec] > 0 && dist[nod] + cost[nod][vec] + aux[nod] - aux[vec] < dist[vec]){
					dist[vec] = dist[nod] + cost[nod][vec] + aux[nod] - aux[vec];
					cdist[vec] = cdist[nod] + cost[nod][vec];
					pq.push({dist[vec], vec}), from[vec] = nod;
				}
	}
 
	return(dist[2 * n + 1] != inf);
}

int maxMatch;
double minCost;

void cmcm(double lim){
	maxMatch = 0, minCost = 0;

	for(int i = 0; i <= 2 * n + 1; i++){
		adj[i].clear();
		dist[i] = cdist[i] = aux[i] = 0;
		from[i] = 0;
	}

	for(int i = 1; i <= n; i++){
		adj[0].push_back(i), adj[i + n].push_back(2 * n + 1);
		f[0][i] = 1, f[i + n][2 * n + 1] = 1;
	}

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(cost[i][j + n] <= lim){
				adj[i].push_back(j + n), adj[j + n].push_back(i);
				f[i][j + n] = inf;
			}
	BF();

	while(DJK()){
		int nod = 2 * n + 1, flow = inf;

		while(nod != 0)
			flow = min(flow, f[from[nod]][nod]), nod = from[nod];
 
		nod = 2 * n + 1, maxMatch += flow;
 
		while(nod != 0)
			f[from[nod]][nod] -= flow, f[nod][from[nod]] += flow, nod = from[nod];
		
		minCost += flow * cdist[2 * n + 1];
 
		for(int i = 0; i <= 2 * n + 1; i++)
			aux[i] = dist[i];
	}
}

int main(){

	fin >> n;

	for(int i = 1; i <= n; i++)
		fin >> soldat[i].x >> soldat[i].y;
	for(int i = 1; i <= n; i++)
		fin >> adapost[i].x >> adapost[i].y;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			cost[i][j + n] = calcDist(soldat[i], adapost[j]);
			cost[j + n][i] = -cost[i][j];
		}

	double st = 0, dr = 2000;
	pair <double, double> ans = {0, 0};

	while(dr - st > EPS){
		double mij = (st + dr) / 2;

		cmcm(mij);

		if(maxMatch == n)
			ans = {mij, minCost}, dr = mij;
		else
			st = mij;
	}

	fout << ans.first << ' ' << ans.second << '\n';

	return 0;
}