Algorithms : add 03-algorithms_on_graphs 05-minimum_spanning_tree

12 files changed, 128 insertions, 0 deletions

diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/00_spanning_trees_problems.pdf b/03-algorithms_on_graphs/05-minimum_spanning_tree/00_spanning_trees_problems.pdf
new file mode 100644
index 0000000..060be8b
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/00_spanning_trees_problems.pdf
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
new file mode 100644
index 0000000..f8b58af
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp
@@ -0,0 +1,23 @@
+#include <algorithm>
+#include <iostream>
+#include <iomanip>
+#include <vector>
+#include <cmath>
+
+using std::vector;
+
+double minimum_distance(vector<int> x, vector<int> y) {
+  double result = 0.;
+  //write your code here
+  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;
+}
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01 b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01
new file mode 100644
index 0000000..6261c29
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01
@@ -0,0 +1,5 @@
+4
+0 0
+0 1
+1 0
+1 1
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01.a b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01.a
new file mode 100644
index 0000000..00750ed
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/01.a
@@ -0,0 +1 @@
+3
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02 b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02
new file mode 100644
index 0000000..675fbd8
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02
@@ -0,0 +1,6 @@
+5
+0 0
+0 2
+1 1
+3 0
+3 2
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02.a b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02.a
new file mode 100644
index 0000000..bbea765
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/tests/02.a
@@ -0,0 +1 @@
+7.064495102
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
new file mode 100644
index 0000000..31f00e1
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp
@@ -0,0 +1,28 @@
+#include <algorithm>
+#include <iostream>
+#include <iomanip>
+#include <cassert>
+#include <vector>
+#include <cmath>
+
+using std::vector;
+using std::pair;
+
+
+
+double clustering(vector<int> x, vector<int> y, int k) {
+  //write your code here
+  return -1.;
+} 
+
+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];
+  }
+  std::cin >> k;
+  std::cout << std::setprecision(10) << clustering(x, y, k) << std::endl;
+}
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01 b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01
new file mode 100644
index 0000000..0acb182
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01
@@ -0,0 +1,14 @@
+12
+7 6
+4 3
+5 1
+1 7
+2 7
+5 7
+3 3
+7 8
+2 8
+4 4
+6 7
+2 6
+3
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01.a b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01.a
new file mode 100644
index 0000000..fafa50f
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/01.a
@@ -0,0 +1 @@
+2.828427125
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02 b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02
new file mode 100644
index 0000000..62bb252
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02
@@ -0,0 +1,10 @@
+8
+3 1
+1 2
+4 6
+9 8
+9 9
+8 9
+3 11
+4 12
+4
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02.a b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02.a
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/tests/02.a
@@ -0,0 +1 @@
+5
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/check b/03-algorithms_on_graphs/05-minimum_spanning_tree/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+