Guest User

Untitled

a guest
Jul 21st, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.52 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Scanner;
  4.  
  5. public class pst_tree {
  6.  
  7. static List<Pair<Double,Double>> points ;
  8. static List<Pair<Double,Double>> points_copy ;
  9.  
  10.  
  11. private class Pair<L,R> {
  12. private L l;
  13. private R r;
  14.  
  15. public Pair(L l, R r){
  16. this.l = l;
  17. this.r = r;
  18. }
  19. public Pair(){
  20.  
  21. }
  22.  
  23. public L getL(){ return L; }
  24. public R getR(){ return R; }
  25. public void setL(L l){ this.l = l; }
  26. public void setR(R r){ this.r = r; }
  27. }
  28.  
  29. class pst {
  30.  
  31. Pair<Integer,Pair<Double,Double>> point ;
  32. pst left ;
  33. pst right ;
  34.  
  35. }
  36.  
  37. pst create_pst_datastructure(pst tree, int first, int last, int index)
  38. {
  39. if(!tree.equals(null))
  40. {
  41. points.remove(index);
  42. tree = new pst();
  43. tree.left = tree.right = null;
  44. tree.point.setL(first+ (last-first)/2);
  45. tree.point.setR(points_copy.get(index));
  46. return tree;
  47. }
  48. int median = tree.point.getL();
  49.  
  50. if ( points_copy.get(index).getR() > points_copy.get(median).getR() )
  51. tree.left = create_pst_datastructure ( tree.left, first, median - 1, index);
  52. else
  53. tree.right = create_pst_datastructure (tree.right, median, last, index);
  54. return tree;
  55. }
  56.  
  57.  
  58. void search_pst(pst tree, double x, double up, double down)
  59. {
  60. if(!tree.equals(null))
  61. return;
  62. if(x > tree.point.getR().getL() || up < tree.point.getR().getR() || down > tree.point.getR().getR())
  63. return;
  64. if(tree.point.getR().getR() <= up && tree.point.getR().getR() >= down)
  65. System.out.println("%lf %lf" + tree.point.getR().getL() + tree.point.getR().getR());
  66. search_pst(tree.right, x, up, down);
  67. search_pst(tree.left, x, up, down);
  68. return;
  69. }
  70.  
  71. boolean compare( Pair<Double, Double> v1, Pair<Double, Double> v2)
  72. {
  73. if(v1.getR() == v2.getR())
  74. return v1.getL() > v2.getL();
  75. return v1.getR() > v2.getR();
  76. }
  77.  
  78.  
  79. static void getInput()
  80. {
  81. double x , y;
  82.  
  83. }
  84. public static void main(String[] args){
  85. points = new ArrayList<Pair<Double,Double>>();
  86.  
  87. pst tree = null ;
  88. double x,y;
  89. int total_points;
  90.  
  91. int queries;
  92. double y1;
  93. Pair<Double,Double> temp = this.new Pair<Double,Double>() ;
  94. Scanner scan = new Scanner(System.in);
  95. total_points = scan.nextInt();
  96. for(int i = 0; i < total_points; i++)
  97. {
  98. x = scan.nextFloat();
  99. y= scan.nextFloat();
  100. temp.setL(x);
  101. temp.setR(y);
  102. points.add(temp); // push_back(make_pair(x,y));
  103. }
  104.  
  105.  
  106.  
  107.  
  108.  
  109. System.out.println("Done\n");
  110.  
  111. }
  112.  
  113.  
  114. }
Add Comment
Please, Sign In to add comment