Участник:Kachanov vv/EC MODE

Перейти к: навигация, поиск
```#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;
const int max_value = 1000010;

class Solver {
public:
Solver(int N, double R, int W, double U, double V) :
N(N), R(R), W(W), U(U), V(V) {}

void init() {
city.clear();
for (int i = 0; i < max_value; i++) {
parent[i] = i;
}
for (int i = 1; i <= N; i++) {
cin >> x >> y;
city.emplace_back(make_pair(x, y));
}
ans0 = 0;
ans1 = 0;
}

void process() {
calculateDistance();

components = N;

unite(from, to);
if (components == W || components == 1)
break;
}
}

int find(int a) {
if (parent[a] != a) {
parent[a] = find(parent[a]);
}
return parent[a];
}

void unite(int a, int b) {

int u = find(a);
int v = find(b);
if (u == v)
return;
parent[u] = v;
if (type == 0)
ans0 += cost;
else ans1 += cost;
components--;

}

void calculateDistance() {
double d, diff_x, diff_y;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
diff_x = city[i].first - city[j].first;
diff_y = city[i].second - city[j].second;
d = hypot(diff_x, diff_y);
if (d <= R) {
cost = d * U;
type = 0;
} else {
cost = d * V;
type = 1;
}
make_pair(cost, type),
make_pair(i, j)));
}
}
}

void dump(int t) {
cout << "Caso #" << t << ": " <<
fixed << setprecision(3) << ans0 << " " << ans1 << endl;
}

private:
int components;
int parent[max_value];
int to, from, type, N, W;
double x, y, cost, R, U, V;
double ans0, ans1;
vector<pair<double, double>> city;
vector<pair<pair<double, int>, pair<int, int> > > roads;
};

int main() {
int T, N, W;
double R, U, V;
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> N >> R >> W >> U >> V;
Solver solver(N, R, W, U, V);
solver.init();
solver.process();
solver.dump(t);
}
}```