diff options
Diffstat (limited to '03-algorithms_on_graphs')
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 Binary files differnew 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 + |