Pagini recente » Cod sursa (job #269621) | Cod sursa (job #1987285) | Cod sursa (job #1280529) | Cod sursa (job #2937482)
/// trimisa sa vad daca pica in timp ce am fct pana acum
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in ("adapost.in");
ofstream out ("adapost.out");
const int max_size = 8e2 + 9;
const double INF = 1e9 + 1;
struct str{
int nod;
double val;
bool operator < (const str &aux) const
{
return val > aux.val;
}
};
#define pdd pair <double, double>
double cap[max_size][max_size], cost[max_size][max_size], d[max_size][max_size], aux[max_size];
int t[max_size], dr[max_size], st[max_size], n;
pdd sld[max_size], adp[max_size];
bitset <max_size> viz;
vector <int> mc[max_size];
priority_queue <str> pq;
void bf ()
{
}
bool djk ()
{
}
bool pairup (int nod)
{
}
bool verif (int x)
{
for (int i = 1; i <= 2 * n + 2; i++)
{
mc[i].clear();
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (d[i][j] <= x)
{
mc[1].push_back(i + 1);
mc[i + 1].push_back(1);
mc[i + 1].push_back(n + j + 1);
mc[n + j + 1].push_back(i + 1);
mc[n + j + 1].push_back(2 * n + 2);
mc[2 * n + 2].push_back(n + j + 1);
cap[i + 1][j + n + 1] = d[i][j];
cap[j + n + 1][i + 1] = -d[i][j];
cost[i + 1][j + n + 1] = 1;
cost[1][i + 1] = 1;
cost[j + n + 1][2 * n + 2] = 1;
}
}
}
bool ok = false;
while (1)
{
for (int i = 1; i <= 2 * n + 2; i++)
{
viz[i] = 0;
}
ok = false;
for (int i = 2; i <= n + 1; i++)
{
if (st[i] == 0)
{
ok |= pairup(i);
}
}
if (!ok)
{
break;
}
}
int ct = 0;
for (int i = 2; i <= n + 1; i++)
{
if (st[i] > 0)
{
ct++;
}
}
return (ct == n);
}
int main ()
{
in >> n;
for (int i = 1; i <= n; i++)
{
in >> sld[i].first >> sld[i].second;
}
for (int i = 1; i <= n; i++)
{
in >> adp[i].first >> adp[i].second;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
d[i][j] = sqrt((sld[i].first - adp[j].first) * (sld[i].first - adp[j].first) + (sld[i].second - adp[j].second) * (sld[i].second - adp[j].second));
}
}
int ans = 0;
for (int e = 20; e >= 0; e--)
{
if (verif(ans + (1 << e)))
{
ans += (1 << e);
}
}
}