Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <time.h>
- #include <vector>
- #include <string>
- #include <set>
- #include <utility>
- #include <algorithm>
- #include <queue>
- #include <iomanip>
- #include <cmath>
- #include <limits>
- using std::vector;
- using std::cout;
- using std::endl;
- using std::cin;
- using std::string;
- using std::set;
- using std::pair;
- using std::make_pair;
- using std::min;
- using std::queue;
- struct edge {
- int number;
- int from;
- int to;
- long long weight;
- edge(int number, int from, int to, long long weight) :
- number(number),
- from(from),
- to(to),
- weight(weight) {}
- };
- vector<int> findcomp(int number, vector<vector<int>> &gg) {
- vector<bool> visited(number, false);
- vector<int> comp(number + 1, -1);
- int cur = 0;
- for (int iii = 0; iii < number; ++iii) {
- if (!visited[iii]) {
- queue<int> q;
- q.push(iii);
- while (!q.empty()) {
- int vv = q.front();
- q.pop();
- visited[vv] = true;
- comp[vv] = cur;
- for (uint64_t j = 0; j < gg[vv].size(); ++j) {
- if (!visited[gg[vv][j]])
- q.push(gg[vv][j]);
- }
- }
- cur++;
- }
- }
- comp[number] = cur;
- return comp;
- }
- vector<edge> boruvka(uint64_t number, vector<edge> &edges) {
- int mm = edges.size();
- edges.push_back(edge(0, 0, 0, std::numeric_limits<long long>::max()));
- vector<vector<int>> gg(number, vector<int>(0));
- vector<edge> ttt(0, edge(0, 0, 0, 0));
- vector<bool> visited(mm, false);
- vector<int> comp(number + 1, 0);
- while (ttt.size() < number - 1) {
- comp = findcomp(number, gg);
- int kol = comp[number];
- vector<int> minEdge(kol, mm);
- for (uint64_t ii = 0; ii < edges.size(); ++ii) {
- int compF = comp[edges[ii].from], compS = comp[edges[ii].to];
- if (compF != compS) {
- if ((edges[minEdge[compF]].weight > edges[ii].weight) ||
- (edges[minEdge[compF]].weight) ==
- (edges[ii].weight && edges[minEdge[compF]].number > edges[ii].number)) {
- minEdge[compF] = ii;
- }
- if ((edges[minEdge[compS]].weight > edges[ii].weight) ||
- ((edges[minEdge[compS]].weight == edges[ii].weight) &&
- (edges[minEdge[compS]].number > edges[ii].number))) {
- minEdge[compS] = ii;
- }
- }
- }
- for (int i = 0; i < kol; ++i) {
- if (!visited[minEdge[i]]) {
- visited[minEdge[i]] = true;
- ttt.push_back(edges[minEdge[i]]);
- gg[edges[minEdge[i]].from].push_back(edges[minEdge[i]].to);
- gg[edges[minEdge[i]].to].push_back(edges[minEdge[i]].from);
- }
- }
- }
- return ttt;
- }
- int main() {
- int number;
- cin >> number;
- vector<pair<long long, long long>> coord(number);
- for (int i = 0; i < number; ++i) {
- cin >> coord[i].first >> coord[i].second;
- }
- edge nll(0, 0, 0, 0);
- int medg = number * number;
- vector<edge> edges(medg, nll), mst;
- int edgenumber = 0;
- for (int i = 0; i < number; ++i) {
- for (int j = 0; j < number; ++j) {
- long long val = (coord[i].first - coord[j].first) *
- (coord[i].first - coord[j].first) +
- (coord[i].second - coord[j].second) *
- (coord[i].second - coord[j].second);
- edges[edgenumber] = edge(edgenumber, i, j, val);
- edgenumber = edgenumber + 1;
- }
- }
- mst = boruvka(number, edges);
- double ss = 0;
- for (uint64_t i = 0; i < mst.size(); ++i) {
- ss = std::max(ss, sqrt(mst[i].weight));
- }
- cout << std::fixed << std::setprecision(10) << ss;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement