From 38b23620954f142ccf6653a58c47ff04d516be9c Mon Sep 17 00:00:00 2001
From: cathook <b01902109@csie.ntu.edu.tw>
Date: Wed, 23 Apr 2014 00:19:10 +0800
Subject: add footer, test

---
 _test/meowpp_VP_Tree.cpp |  4 ++--
 footer.asciidoc          | 19 +++++++++++++++++++
 meowpp/dsa/VP_Tree.h     |  4 +++-
 meowpp/dsa/VP_Tree.hpp   | 31 -------------------------------
 4 files changed, 24 insertions(+), 34 deletions(-)

diff --git a/_test/meowpp_VP_Tree.cpp b/_test/meowpp_VP_Tree.cpp
index 8d5e903..34c979c 100644
--- a/_test/meowpp_VP_Tree.cpp
+++ b/_test/meowpp_VP_Tree.cpp
@@ -10,8 +10,8 @@
 #include <queue>
 
 static int N = 100000;
-static int D = 64;
-static int MAX = 100;
+static int D = 32;
+static int MAX = 1000;
 
 typedef long long lnt;
 
diff --git a/footer.asciidoc b/footer.asciidoc
index b6e1ea9..a6301ee 100644
--- a/footer.asciidoc
+++ b/footer.asciidoc
@@ -1,5 +1,24 @@
 
 == Test
+=== ACM 相關題目
+[options="header",width="70%",cols="3<s,3<,4^,1^,1<,2^m",grid="rows"]
+|=======================================================================
+| Name          | Problem               | Link  | Status | Time | source
+| KD_Tree       | 'Retrenchment' |
+http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ]
+https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live]
+| Accept | 0.083 | http://codepad.org/U85ruse5[codepad]
+
+
+| VP_Tree       | 'Retrenchment' |
+http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ]
+https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live]
+| Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad]
+
+
+|=======================================================================
+
+
 
 
 == Bug Report / Contact
diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h
index 669eb0f..1877b74 100644
--- a/meowpp/dsa/VP_Tree.h
+++ b/meowpp/dsa/VP_Tree.h
@@ -158,7 +158,9 @@ namespace meow{
   //#
   //#[NOTE]
   //#========================================
-  //# * 實測結果發覺比 `KD_Tree` 有效率多了...
+  //# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有
+  //#   'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到
+  //#   一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響
   //# * 'TODO' `insert()`, `erase()` 算是未完成功能
   //#
   //#========================================
diff --git a/meowpp/dsa/VP_Tree.hpp b/meowpp/dsa/VP_Tree.hpp
index a3a0d82..ba97ad7 100644
--- a/meowpp/dsa/VP_Tree.hpp
+++ b/meowpp/dsa/VP_Tree.hpp
@@ -66,7 +66,6 @@ namespace meow{
   inline Scalar
   VP_Tree<Vector, Scalar>::split(ssize_t __first, ssize_t __last,
                                  size_t __order, Vector const& __center){
-    //printf("%ld %ld %lu\n", __first, __last, __order);
     ssize_t first0 = __first;
     ssize_t last0  = __last;
     ssize_t order0 = __order;
@@ -77,21 +76,6 @@ namespace meow{
     while(__first < __last){
       size_t threshold_index = __first + rand() % (__last - __first + 1);
       Scalar threshold(dist2[threshold_index - first0]);
-      /*
-      printf("range(%ld, %ld) dist2 = %3lld from %d\n",
-             __first - first0, __last - first0,
-             threshold, threshold_index - first0);
-      for(int i = first0; i <= last0; i++){
-        if(i == __first) printf("+");
-        if(i == threshold_index) printf("<");
-        printf("<%lld,%lld,(%lld)>", _vectors[i][0], _vectors[i][1],
-               dist2[i - first0]);
-        if(i == threshold_index) printf(">");
-        if(i == __last) printf("+");
-        printf(" ");
-      }
-      printf("\n");
-      // */
       size_t large_first = __last + 1;
       for(size_t i = __first; __first <= large_first - 1; large_first--){
         if(threshold < dist2[large_first - 1 - first0]) continue;
@@ -121,21 +105,6 @@ namespace meow{
         }
       }
     }
-    /*
-    for(int i = first0; i <= last0; i++){
-      if(i == __first) printf("+");
-      if(i - first0 == order0) printf("<");
-      printf("<%lld,%lld,(%lld)>", _vectors[i][0], _vectors[i][1],
-             dist2[i - first0]);
-      if(i - first0 == order0) printf(">");
-      if(i == __first) printf("+");
-      printf(" ");
-    }
-    printf("\n");
-    printf("dist2(from<%lld,%lld>) = %lld\n",
-           __center[0], __center[1],
-           dist2[__first - first0]);
-    // */
     return dist2[__first - first0];
   }
   ////////////////////// **# build() #** ///////////////////
-- 
cgit