diff options
| -rw-r--r-- | 03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp | 106 | ||||
| -rw-r--r-- | 03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp | 105 |
2 files changed, 192 insertions, 19 deletions
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp index f8b58af..7cf3bef 100644 --- a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp +++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp @@ -6,18 +6,104 @@ using std::vector; -double minimum_distance(vector<int> x, vector<int> y) { - double result = 0.; - //write your code here - return result; -} +struct Vertex +{ + int a; + int b; + double l; + + static int compare(Vertex &a, Vertex &b) + { + return (a.l < b.l); + } + + void print() + { + std::cout << a << ";" << b << " " << l << std::endl; + } +}; + +struct Point +{ + int x; + int y; + int parent; + + void print() + { + std::cout << x << ";" << y << " " << parent << std::endl; + } +}; + +struct Points +{ + vector<Point> points; + vector<Vertex> vertices; + + Points(int n) : points(n), vertices(n*n) { } + + void read(int i) + { + std::cin >> points[i].x >> points[i].y; + points[i].parent = i; + } + + void print() + { + for (int i = 0; i < points.size(); i++) + points[i].print(); + } + + int find(int i) + { + if (points[i].parent == i) + return i; + points[i].parent = find(points[i].parent); + return points[i].parent; + } + + double solve() + { + int x = 0; + for (int i = 0; i < points.size(); i++) { + for (int j = i + 1; j < points.size(); j++) { + vertices[x].a = i; + vertices[x].b = j; + vertices[x].l = sqrt( + (points[i].x - points[j].x) * (points[i].x - points[j].x) + + + (points[i].y - points[j].y) * (points[i].y - points[j].y) + ); + x += 1; + } + } + vertices.resize(x); + + std::sort(vertices.begin(), vertices.end(), Vertex::compare); + + int n = 0; + double result = 0.; + for (int i = 0; i < vertices.size(); i++) { + int realA = find(vertices[i].a); + int realB = find(vertices[i].b); + if (realA != realB) { + result += vertices[i].l; + n += 1; + if (n == points.size()) + break; + points[realB].parent = realA; + } + } + + return result; + } +}; int main() { size_t n; std::cin >> n; - vector<int> x(n), y(n); - for (size_t i = 0; i < n; i++) { - std::cin >> x[i] >> y[i]; - } - std::cout << std::setprecision(10) << minimum_distance(x, y) << std::endl; + Points points(n); + for (size_t i = 0; i < n; i++) + points.read(i); + std::cout << std::setprecision(10) << points.solve() << std::endl; } diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp index 31f00e1..167dc5c 100644 --- a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp +++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp @@ -9,20 +9,107 @@ using std::vector; using std::pair; +struct Vertex +{ + int a; + int b; + double l; -double clustering(vector<int> x, vector<int> y, int k) { - //write your code here - return -1.; -} + static int compare(Vertex &a, Vertex &b) + { + return (a.l < b.l); + } + + void print() + { + std::cout << a << ";" << b << " " << l << std::endl; + } +}; + +struct Point +{ + int x; + int y; + int parent; + + void print() + { + std::cout << x << ";" << y << " " << parent << std::endl; + } +}; + +struct Points +{ + vector<Point> points; + vector<Vertex> vertices; + + Points(int n) : points(n), vertices(n*n) { } + + void read(int i) + { + std::cin >> points[i].x >> points[i].y; + points[i].parent = i; + } + + void print() + { + for (int i = 0; i < points.size(); i++) + points[i].print(); + } + + int find(int i) + { + if (points[i].parent == i) + return i; + points[i].parent = find(points[i].parent); + return points[i].parent; + } + + double solve(int k) + { + int x = 0; + for (int i = 0; i < points.size(); i++) { + for (int j = i + 1; j < points.size(); j++) { + vertices[x].a = i; + vertices[x].b = j; + vertices[x].l = sqrt( + (points[i].x - points[j].x) * (points[i].x - points[j].x) + + + (points[i].y - points[j].y) * (points[i].y - points[j].y) + ); + x += 1; + } + } + vertices.resize(x); + + std::sort(vertices.begin(), vertices.end(), Vertex::compare); + + int n = 0; + double result = 0.; + for (int i = 0; i < vertices.size(); i++) { + int realA = find(vertices[i].a); + int realB = find(vertices[i].b); + if (realA != realB) { + if (n == points.size() - k) { + result = vertices[i].l; + break; + } + n += 1; + points[realB].parent = realA; + } + } + + return result; + } +}; int main() { size_t n; int k; std::cin >> n; - vector<int> x(n), y(n); - for (size_t i = 0; i < n; i++) { - std::cin >> x[i] >> y[i]; - } + Points points(n); + for (size_t i = 0; i < n; i++) + points.read(i); std::cin >> k; - std::cout << std::setprecision(10) << clustering(x, y, k) << std::endl; + std::cout << std::setprecision(10) << points.solve(k) << std::endl; } |