Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <cmath>
- double edge_weight(std::pair<int, int> a, std::pair<int, int> b) {
- return std::sqrt((a.first - b.first)^2 + (a.second - b.second)^2);
- }
- double kruskal(int ver_num, std::vector<std::pair<double, std::pair<int, int>>>& edges) {
- size_t edge_num = edges.size();
- std::sort(std::begin(edges), std::end(edges));
- std::vector<int> treeId(ver_num);
- for (int32_t i = 0; i < ver_num; i++) {
- treeId[i] = i;
- }
- double mstCost = 0;
- std::vector<std::pair<int, std::pair<int, int>>> edgesInMST;
- for (int i = 0; i < edge_num; i++) {
- int firstVer = edges[i].second.first, secVer = edges[i].second.second;
- double cost = edges[i].first;
- if (treeId[firstVer] != treeId[secVer]) {
- edgesInMST.emplace_back(std::make_pair(cost, std::make_pair(firstVer, secVer)));
- mstCost += cost;
- int oldTree = treeId[firstVer];
- for (int j = 0; j < ver_num; ++j) {
- if (treeId[j] == oldTree)
- treeId[j] = treeId[secVer];
- }
- }
- }
- return mstCost;
- }
- int main() {
- int num_terminal, num_extra;
- std::cin >> num_terminal >> num_extra;
- std::vector<std::pair<int, int> > vertices(num_terminal);
- std::vector<std::pair<int, int> > added_vertices;
- std::vector<std::pair<double, std::pair<int, int> > > edges;
- for (int i = 0; i != num_terminal; ++i) {
- std::cin >> vertices[i].first >> vertices[i].second;
- }
- int right = 100000;
- int down = 100000;
- int up = -1;
- int left = -1;
- for (int j = 0; j != num_terminal; ++j) {
- if (right > vertices[j].first) {
- right = vertices[j].first;
- }
- if (down > vertices[j].second) {
- down = vertices[j].second;
- }
- if (up < vertices[j].second) {
- up = vertices[j].second;
- }
- if (left < vertices[j].first) {
- left = vertices[j].first;
- }
- }
- for (int i = 0; i != num_terminal; ++i) {
- for (int j = i + 1; j < num_terminal; ++j) {
- edges.push_back(std::make_pair(edge_weight(vertices[i], vertices[j]), std::make_pair(i, j)));
- }
- }
- double best_mst = kruskal(num_terminal, edges);
- int new_num_vert = num_terminal;
- int step1 = 1;
- int step2 = 1;
- if (right - left >= 1000) {
- step1 = (right - left) / 300;
- }
- if (up - down >= 1000) {
- step2 = (up - down) / 400;
- }
- for (int i = up; i != down; i += step1) {
- for (int j = left; j != right && num_extra != 0; j += step2) {
- std::vector<std::pair<double, std::pair<int, int> > > copy_edges = edges;
- std::pair<int, int> possible_vert = std::make_pair(i, j);
- for(int k = 0; k != new_num_vert; ++k) {
- copy_edges.push_back(std::make_pair(edge_weight(possible_vert, vertices[k]), std::make_pair(k, new_num_vert)));
- }
- double loc_mst = kruskal(new_num_vert + 1, copy_edges);
- if (loc_mst < best_mst) {
- best_mst = loc_mst;
- edges = copy_edges;
- --num_extra;
- ++new_num_vert;
- vertices.push_back(possible_vert);
- added_vertices.push_back(possible_vert);
- }
- }
- }
- std::cout << added_vertices.size() << "\n";
- for (auto x : added_vertices) {
- std::cout << x.first << " " << x.second << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement