佳音的博客

2010/01/19

herding frosh 算法

Filed under: Uncategorized — 佳音 @ 7:33 上午
  1.  
  2. package programming.challenges;
  3. import java.util.Arrays;
  4. /**
  5. * Created by IntelliJ IDEA.
  6. * User: zhangjiayin
  7. * Date: Jan 13, 2010
  8. * Time: 7:15:50 PM
  9. * To change this template use File | Settings | File Templates.
  10. */
  11. public class HerdingTrees {
  12. private Tree origin = new Tree(0, 0);
  13. /**
  14. * get min value of a and b
  15. * @param a
  16. * @param b
  17. * @return
  18. */
  19. private static double min(double a, double b) {
  20. return a > b ? b : a;
  21. }
  22. /**
  23. * “vector o p1″ cross “vector o p2″
  24. * @param o
  25. * @param p1
  26. * @param p2
  27. * @return
  28. */
  29. private static double cross(Tree o , Tree p1, Tree p2) {
  30. return (p1.x – o.x) * (p2.y – o.y) – (p1.y – o.y) * (p2.x – o.x);
  31. }
  32. /**
  33. *  ”vector p1″ cross “vector p2″
  34. * @param p1
  35. * @param p2
  36. * @return
  37. */
  38. private static double cross(Tree p1, Tree p2) {
  39. return p1.x * p2.y – p1.y * p2.x;
  40. }
  41. /**
  42. * distance of two tree p2 and p1
  43. * @param p1
  44. * @param p2
  45. * @return
  46. */
  47. private static double getDistance(Tree p1, Tree p2) {
  48. return Math.sqrt(Math.pow(p1.x – p2.x, 2) + Math.pow(p1.y – p2.y, 2));
  49. }
  50. /**
  51. * sort by angle in polar coordinate system
  52. * if the angle is the same, then sort by their length
  53. * @param p1
  54. * @param p2
  55. * @return
  56. */
  57. public static boolean sortByAngle(Tree p1, Tree p2) {
  58. if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
  59. if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
  60. if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
  61. if (p1.y * p2.y < 0) return p1.y > p2.y;
  62. double c = cross(p1, p2);
  63. return c > 0 || c == 0 && Math.abs(p1.x) < Math.abs(p2.x);
  64. }
  65. /**
  66. *  determine if o -> p1 -> p2 are convex  (refer to the origin)
  67. * @param o
  68. * @param p1
  69. * @param p2
  70. * @return
  71. */
  72. private boolean convex(Tree o, Tree p1,Tree p2) {
  73. double c = cross(o, p1, p2);
  74. return c > 0 || c == 0 && ((p1.x – o.x) * (p2.x – p1.x) + (p1.y – o.y) * (p2.y – p1.y)) < 0;
  75. }
  76. /**
  77. * instance of this algorithm
  78. * @param trees
  79. * @return
  80. */
  81. public double goaround(Tree[] trees) {
  82. int[] hulls = new int[1000];
  83. int i, j, k;
  84. int treesCount = trees.length;
  85. // the special case
  86. if (treesCount == 0) {
  87. return 2.0;
  88. }
  89. // sort all trees by their angle in polar coordinate system
  90. Arrays.sort(trees);
  91. double ans = 1e9;
  92. // start from each possible tree
  93. for (i=0; i<treesCount; ++i) {
  94. // get a proper hull by the graham’s scan
  95. k = 0;
  96. for (j=0; j< treesCount; ++j) {
  97. int p = (i+j) % treesCount;
  98. while (k >= 2 && !convex(trees[hulls[k-2]], trees[hulls[k-1]], trees[p])) k–;
  99. hulls[k++] = p;
  100. }
  101. // calculate the distance of the hull
  102. double length = getDistance(trees[i], origin) + getDistance(trees[(i-1+treesCount)%treesCount], origin);
  103. for (j=0; j<k-1; ++j)
  104. length += getDistance(trees[hulls[j]], trees[hulls[j+1]]);
  105. // record the minimal distance
  106. ans = min(ans, length);
  107. }
  108. // print solution, don’t forget to plus 2
  109. return 2.0 + ans;
  110. }
  111. public static void main(String[] argv) {
  112. Tree [] trees =  {new Tree(1,1),new  Tree(-1,1), new Tree(-1, -1), new Tree(1,-1)};
  113. double a = new HerdingTrees().goaround(trees);
  114. System.out.println(a);
  115. Tree [] trees2 =  {new Tree(1,1),new  Tree(-1,1), new Tree(-1, -1), new Tree(1,-1), new Tree(1,-20)};
  116. double b = new HerdingTrees().goaround(trees2);
  117. System.out.println(b);
  118. }
  119. }
  120. class Tree implements Comparable<Tree> {
  121. public double x = 0;
  122. public double y = 0;
  123. public Tree(int x, int y) {
  124. this.x = x;
  125. this.y = y;
  126. }
  127. public int compareTo(Tree p) {
  128. return HerdingTrees.sortByAngle(this, p) ? 0 : 1;
  129. }
  130. }
  131. package programming.challenges;
  132. import java.util.Arrays;
  133. /** * Created by IntelliJ IDEA. * User: zhangjiayin * Date: Jan 13, 2010 * Time: 7:15:50 PM * To change this template use File | Settings | File Templates. */public class HerdingTrees {
  134. private Tree origin = new Tree(0, 0);    /**     * get min value of a and b     * @param a     * @param b     * @return     */    private static double min(double a, double b) {        return a > b ? b : a;    }
  135. /**     * “vector o p1″ cross “vector o p2″     * @param o     * @param p1     * @param p2     * @return     */    private static double cross(Tree o , Tree p1, Tree p2) {        return (p1.x – o.x) * (p2.y – o.y) – (p1.y – o.y) * (p2.x – o.x);    }
  136. /**     *  ”vector p1″ cross “vector p2″     * @param p1     * @param p2     * @return     */    private static double cross(Tree p1, Tree p2) {        return p1.x * p2.y – p1.y * p2.x;    }
  137. /**     * distance of two tree p2 and p1     * @param p1     * @param p2     * @return     */    private static double getDistance(Tree p1, Tree p2) {        return Math.sqrt(Math.pow(p1.x – p2.x, 2) + Math.pow(p1.y – p2.y, 2));    }
  138.  
  139. /**     * sort by angle in polar coordinate system     * if the angle is the same, then sort by their length     * @param p1     * @param p2     * @return     */    public static boolean sortByAngle(Tree p1, Tree p2) {
  140. if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
  141. if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
  142. if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
  143. if (p1.y * p2.y < 0) return p1.y > p2.y;
  144. double c = cross(p1, p2);
  145. return c > 0 || c == 0 && Math.abs(p1.x) < Math.abs(p2.x);    }
  146. /**     *  determine if o -> p1 -> p2 are convex  (refer to the origin)     * @param o     * @param p1     * @param p2     * @return     */    private boolean convex(Tree o, Tree p1,Tree p2) {        double c = cross(o, p1, p2);        return c > 0 || c == 0 && ((p1.x – o.x) * (p2.x – p1.x) + (p1.y – o.y) * (p2.y – p1.y)) < 0;    }
  147. /**     * instance of this algorithm     * @param trees     * @return     */    public double goaround(Tree[] trees) {
  148. int[] hulls = new int[1000];
  149. int i, j, k;
  150. int treesCount = trees.length;
  151.  
  152. // the special case        if (treesCount == 0) {            return 2.0;        }
  153.  
  154. // sort all trees by their angle in polar coordinate system        Arrays.sort(trees);
  155. double ans = 1e9;
  156. // start from each possible tree        for (i=0; i<treesCount; ++i) {
  157. // get a proper hull by the graham’s scan            k = 0;            for (j=0; j< treesCount; ++j) {                int p = (i+j) % treesCount;                while (k >= 2 && !convex(trees[hulls[k-2]], trees[hulls[k-1]], trees[p])) k–;                hulls[k++] = p;            }
  158. // calculate the distance of the hull            double length = getDistance(trees[i], origin) + getDistance(trees[(i-1+treesCount)%treesCount], origin);            for (j=0; j<k-1; ++j)                length += getDistance(trees[hulls[j]], trees[hulls[j+1]]);
  159. // record the minimal distance            ans = min(ans, length);
  160. }
  161. // print solution, don’t forget to plus 2
  162. return 2.0 + ans;    }
  163. public static void main(String[] argv) {        Tree [] trees =  {new Tree(1,1),new  Tree(-1,1), new Tree(-1, -1), new Tree(1,-1)};        double a = new HerdingTrees().goaround(trees);        System.out.println(a);
  164. Tree [] trees2 =  {new Tree(1,1),new  Tree(-1,1), new Tree(-1, -1), new Tree(1,-1), new Tree(1,-20)};        double b = new HerdingTrees().goaround(trees2);        System.out.println(b);
  165. }}
  166. class Tree implements Comparable<Tree> {        public double x = 0;
  167. public double y = 0;
  168. public Tree(int x, int y) {        this.x = x;        this.y = y;    }
  169. public int compareTo(Tree p) {        return HerdingTrees.sortByAngle(this, p) ? 0 : 1;
  170.  
  171. }
  172.  
  173. }
  174.  

没有评论 »

还没有评论呢。

这篇文章上的评论的 RSS feed TrackBack URL

留下评论

Powered by 00RZ