#include #include #include #include #include using namespace std; using Pos = pair; template T sqr(T x) { return x * x; } const int INF = 1e9; double LenPos(const Pos& a, const Pos& b) { return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second)); } int FindParent(vector& parents, int node) { if (node != parents[node]) parents[node] = FindParent(parents, parents[node]); return parents[node]; } void UnionNode(vector& parents, int n1, int n2) { int pa = FindParent(parents, n1); int pb = FindParent(parents, n2); if (pa == pb) return; parents[pa] = pb; return; } double MST(int n, const vector>>& edges) { vector parents(n + 1); for (int i = 0; i <= n; i++) parents[i] = i; double res = 0; int m = edges.size(); for (int i = 0; i < m; i++) { auto [cost, edge] = edges[i]; if (FindParent(parents, edge.first) == FindParent(parents, edge.second)) continue; res += cost; UnionNode(parents, edge.first, edge.second); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector pos(n); for (Pos& p : pos) cin >> p.first >> p.second; vector>> edges; vector order(n); for (int i = 0; i < n; i++) order[i] = i; sort(order.begin(), order.end(), [&pos](int a, int b) { return pos[a].first < pos[b].first; }); for (int i = 0; i < n - 1; i++) { int u = order[i]; for (int j = 1; j <= 3 && i + j < n; j++) { int v = order[i + j]; edges.push_back({ LenPos(pos[u], pos[v]), {u, v} }); } } sort(order.begin(), order.end(), [&pos](int a, int b) { return pos[a].second < pos[b].second; }); for (int i = 0; i < n - 1; i++) { int u = order[i]; for (int j = 1; j <= 3 && i + j < n; j++) { int v = order[i + j]; edges.push_back({ LenPos(pos[u], pos[v]), {u, v} }); } } pos.clear(); sort(edges.begin(), edges.end()); cout << fixed << setprecision(2); cout << MST(n, edges) << '\n'; return 0; }

제출 #144802

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

체커 출력: