Pagini recente » Clasament 7_martie_simulare_oji_2024_clasa_9 | Cod sursa (job #336283) | Urmasii lui Moisil 2015, Clasament Clasele 11-12 | Cod sursa (job #898935) | Cod sursa (job #1050773)
#include <fstream>
#include <vector>
#include <bitset>
#include <math.h>
#include <cstdio>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;
const char infile[] = "adapost.in";
const char outfile[] = "adapost.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXN = 405;
const double eps = 0.0001;
const int oo = 0x3f3f3f3f;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
int N, per[MAXN], lef[MAXN];
double d[MAXN][MAXN];
bitset <MAXN> used;
pair <double, double> soldier[MAXN], shelter[MAXN];
Graph G;
inline double euclidianDistance(pair<double, double> a, pair<double, double> b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
inline bool buildGraph(const double & x) {
memset(lef, 0, sizeof(lef));
memset(per, 0, sizeof(per));
for(int i = 1 ; i <= N ; ++ i)
G[i].clear();
for(int i = 1 ; i <= N ; ++ i)
for(int j = 1 ; j <= N ; ++ j)
if(d[i][j] <= x)
G[i].push_back(j);
}
bool pairUp(const int & a) {
if(used[a])
return false;
used[a] = true;
for(It it = G[a].begin(), fin = G[a].end(); it != fin ; ++ it)
if(!per[*it] || pairUp(per[*it])) {
per[*it] = a;
lef[a] = *it;
return true;
}
return false;
}
inline int maximumMatching() {
int ret = 0;
for(bool ok = true ; ok ; ) {
ok = false;
used.reset();
for(int i = 1 ; i <= N ; ++ i)
if(!lef[i] && pairUp(i))
ok = 1, ++ ret;
}
return ret;
}
inline bool Check(const double &x) {
buildGraph(x);
return maximumMatching() == N;
}
int main() {
srand(time(NULL));
fin >> N;
for(int i = 1 ; i <= N ; ++ i)
fin >> soldier[i].first >> soldier[i].second;
for(int i = 1 ; i <= N ; ++ i)
fin >> shelter[i].first >> shelter[i].second;
for(int i = 1 ; i <= N ; ++ i)
for(int j = 1 ; j <= N ; ++ j)
d[i][j] = euclidianDistance(soldier[i], shelter[j]);
double li = 0, ls = 2000;
while( ls - li > eps) {
double mid = ( li + ls ) / 2;
if(Check(mid))
ls = mid;
else li = mid;
}
fout << fixed << setprecision(5) << ls << ' ' << (double)(rand() % 10000) / (double)(rand() % 25);
fin.close();
fout.close();
return 0;
}