Pagini recente » Difprim | Cod sursa (job #3362493) | Borderou de evaluare (job #3362493) | Cod sursa (job #3362081) | Cod sursa (job #3362488)
#include <bits/stdc++.h>
#define f first
#define s second
#define float double
using namespace std;
ifstream fin ("adapost.in");
ofstream fout ("adapost.out");
int n, sink;
long long st, mij, dist, maxflux, cost, iuli, maxd;
float morariu, acc_dist, acc_cost;
pair <float, float> sld[405], adp[405];
struct much{
int c, f;
long long z;
};
much a[805][805];
vector <int> v[805];
int last[805];
long long d[805], dvechi[805], reald[805];
int cuplaj[805];
bool mrc[405];
bool say_gex(int nod, long long dist){ //say gex pt ca fac cupluri de noduri si atunci nodurile fac say gex lol
// si eu cu cezar bolba
// dar el e tsundere
//sunt taken bro sybau
// de mine bro
//ba nu de tudor vianu huzz
// nu mai suntem prieteni
//oricum suntem frati nu ai unde sa pleci
// ok you have a point
if(mrc[nod]) return 0;
mrc[nod] = 1;
for(int i = n + 1; i < sink; i++){
if(a[nod][i].z <= dist && (!cuplaj[i] || say_gex(cuplaj[i], dist))){
cuplaj[nod] = i;
cuplaj[i] = nod;
return 1;
}
}
return 0;
}
//scuzati cearta de mai sus
int fa_cuplaj(long long dist){
int rez = 0;
bool continua = 1;
for(int i = 1; i <= n; i++){
cuplaj[i] = 0;
cuplaj[n+i] = 0;
}
while(continua){
continua = 0;
for(int i = 1; i <= n; i++){
mrc[i] = 0;
}
for(int i = 1; i <= n; i++){
if(!cuplaj[i] && say_gex(i, dist)){
continua = 1;
rez++;
}
}
}
return rez;
}
//Piesa the masque de la edge of sanity ar trebui sa fie una din cele 7 minuni
//A opta minune
//Oare stie domnul Dan Swano sa faca flux maxim de cost minim?
/*void omul_cu_clopot_vad(){
for(int i = 0; i <= sink; i++){
reald[i] = INT_MAX;
mrc[i] = 0;
}
reald[0] = 0;
queue <int> q;
q.push(0);
mrc[0] = 1;
int nod, nxt;
while(!q.empty()){
nod = q.front();
//cout << nod << " ";
q.pop();
for(int i = 0; i < v[nod].size(); i++){
nxt = v[nod][i];
if(reald[nod] + a[nod][nxt].z < reald[nxt]){
reald[nxt] = reald[nod] + a[nod][nxt].z;
if(!mrc[nxt]){
q.push(nxt);
mrc[nxt] = 1;
}
}
}
mrc[nod] = 0;
}
}*/
void omul_cu_clopot_vad(){
for(int i = 0; i <= sink; i++){
reald[i] = INT_MAX;
}
reald[0] = 0;
int nxt;
for(int i = 0; i < sink; i++){
for(int j = 0; j <= sink; j++){
for(int p = 0; p < v[j].size(); p++){
nxt = v[j][p];
if(reald[j] != INT_MAX && reald[j] + a[j][nxt].z < reald[nxt]){
reald[nxt] = reald[j] + a[j][nxt].z;
}
}
}
}
}
void deschistra(){
priority_queue <pair<int, int>, vector <pair<int, int>>, greater <pair<int, int>>> q;
for(int i = 0; i <= sink; i++){
dvechi[i] = reald[i];
d[i] = INT_MAX;
last[i] = -1;
}
d[0] = 0;
reald[0] = 0;
last[0] = -2;
q.push({0, 0});
int nod, dnou, nxt;
while(!q.empty()){
dnou = q.top().first;
nod = q.top().second;
q.pop();
if(dnou != d[nod]){
continue;
}
for(int i = 0; i < v[nod].size(); i++){
nxt = v[nod][i];
if(dnou + a[nod][nxt].z + dvechi[nod] - dvechi[nxt] < d[nxt] &&
a[nod][nxt].f < a[nod][nxt].c){
last[nxt] = nod;
d[nxt] = dnou + a[nod][nxt].z + dvechi[nod] - dvechi[nxt];
reald[nxt] = reald[nod] + a[nod][nxt].z;
q.push({d[nxt], nxt});
}
}
}
}
void fa_un_drum(){
int nod = sink, minim_ude = INT_MAX;
while(last[nod] != -2){
minim_ude = min(minim_ude, a[last[nod]][nod].c - a[last[nod]][nod].f);
nod = last[nod];
}
maxflux += minim_ude;
cost += minim_ude * reald[sink];
nod = sink;
while(last[nod] != -2){
a[last[nod]][nod].f += minim_ude;
a[nod][last[nod]].f -= minim_ude;
nod = last[nod];
}
}
void flux(){
int lastflux = -1;
while(true){
lastflux = maxflux;
deschistra();
if(last[sink] != -1){
fa_un_drum();
}else break;
}
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
fin >> n;
sink = 2 * n + 1;
for(int i = 1; i <= n; i++){
fin >> sld[i].f >> sld[i].s;
a[0][i] = {1, 0, 0};
v[0].push_back(i);
v[i].push_back(0);
}
for(int i = 1; i <= n; i++){
fin >> adp[i].f >> adp[i].s;
for(int j = 1; j <= n; j++){
morariu = sqrt((adp[i].f - sld[j].f) * (adp[i].f - sld[j].f) +
(adp[i].s - sld[j].s) * (adp[i].s - sld[j].s));
morariu *= 1000000;
iuli = morariu;
maxd = max(maxd, iuli);
a[j][n+i] = {1, 0, iuli};
a[n+i][j] = {0, 0, -iuli};
}
a[n+i][sink] = {1, 0, 0};
v[n+i].push_back(sink);
v[sink].push_back(n + i);
}
mij = 1;
while(mij < maxd) mij *= 2;
while(mij >= 1){
//cout << st + mij << " ";
if(fa_cuplaj(st + mij) == n){
dist = st + mij;
}
else{
st += mij;
}
mij /= 2;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(a[i][n+j].z <= dist){
v[i].push_back(n + j);
v[n+j].push_back(i);
}
}
}
omul_cu_clopot_vad();
flux();
acc_dist = dist;
acc_dist /= 1000000;
acc_cost = cost;
acc_cost /= 1000000;
fout << acc_dist << " " << acc_cost;
return 0;
}