Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <unordered_map>
- #include <string>
- #include <vector>
- #include <iostream>
- #include <set>
- #include <queue>
- #include "optimization.h"
- #include <math.h>
- #include <unordered_map>
- #include <iomanip>
- using namespace std;
- struct town {
- int x;
- int y;
- };
- int main() {
- vector<tuple<double, int, int>> edges;
- cout.tie(0);
- cin.tie(0);
- ios_base::sync_with_stdio(0);
- int n = readInt();
- // cin >> n;
- vector<town> towns(n);
- vector<int> id(n);
- vector<vector<int>> sets(n);
- for (int i = 0; i < n; i++) {
- // cin >> towns[i].x >> towns[i].y;
- towns[i].x = readInt(); towns[i].y = readInt();
- id[i] = i;
- sets[i].push_back(i);
- }
- unordered_map<int, double> used_x;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- auto x1 = towns[i].x;
- auto y1 = towns[i].y;
- auto x2 = towns[j].x;
- auto y2 = towns[j].y;
- int x = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
- if (used_x[x] == 0) {
- used_x[x] = sqrt(x);
- }
- edges.emplace_back(used_x[x], i, j);
- }
- }
- double answer = 0;
- sort(edges.begin(), edges.end());
- for (auto[w, a, b]: edges) {
- if (id[a] == id[b]) {
- continue;
- }
- answer += w;
- int small = a;
- if (sets[id[a]].size() > sets[id[b]].size()) {
- small = b;
- }
- int big = a + b - small;
- for (int x: sets[id[small]]) {
- id[x] = id[big];
- sets[id[big]].push_back(x);
- }
- }
- // cout << std::setprecision(10) << answer;
- writeDouble(answer, 10);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement