Pagini recente » Cod sursa (job #2815340) | Cod sursa (job #980893) | Cod sursa (job #287217) | Cod sursa (job #2019956) | Cod sursa (job #3333143)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
#define st first
#define nd second
struct edge
{
int x, y;
double w;
bool operator<(const edge &a) const
{
return w < a.w;
}
};
struct dsu
{
vector<pair<int, int>> set;
dsu(int n) // konstruktor
{
set.resize(n);
for (int i = 0; i < n; i++)
{
set[i].nd = i; // parent
set[i].st = 0; // rank
}
}
int find(int x)
{
if (set[x].nd != x)
set[x].nd = find(set[x].nd);
return set[x].nd;
}
bool unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
return false;
if (set[x].st < set[y].st)
swap(x, y);
set[y].nd = x;
if (set[x].st == set[y].st)
set[x].st++;
return true;
}
};
void merge(vector<edge> &a, vector<edge> &b)
{
int i = 0, j = 0, n = 0;
vector<edge> tmp(a.size() + b.size()); // n lesz az indexe
while (i <= a.size() && j <= b.size())
{
if (a[i])
}
}
int main()
{
int n;
ifstream in("desen.in");
ofstream out("desen.out");
in >> n;
vector<edge> prev;
vector<pair<int, int>> p(n);
for (int i = 0; i < n; i++)
{
vector<edge> edges;
edges.reserve(2 * i);
in >> p[i].first >> p[i].second;
for (int j = 0; j < i; j++)
{
double dx = p[i].first - p[j].first;
double dy = p[i].second - p[j].second;
edges.push_back({i, j, sqrt(dx * dx + dy * dy)});
}
sort(edges.begin(), edges.end());
dsu set(i + 1);
double s = 0;
vector<edge> idk;
idk.reserve(i);
for (auto &e : edges)
{
if ((int)idk.size() == i)
break;
if (set.unite(e.x, e.y))
{
s += e.w;
idk.push_back(e);
}
}
prev = idk;
out << fixed << setprecision(6) << s << '\n';
}
in.close();
out.close();
return 0;
}