Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.List;
- import java.util.Scanner;
- public class pst_tree {
- static List<Pair<Double,Double>> points ;
- static List<Pair<Double,Double>> points_copy ;
- private class Pair<L,R> {
- private L l;
- private R r;
- public Pair(L l, R r){
- this.l = l;
- this.r = r;
- }
- public Pair(){
- }
- public L getL(){ return L; }
- public R getR(){ return R; }
- public void setL(L l){ this.l = l; }
- public void setR(R r){ this.r = r; }
- }
- class pst {
- Pair<Integer,Pair<Double,Double>> point ;
- pst left ;
- pst right ;
- }
- pst create_pst_datastructure(pst tree, int first, int last, int index)
- {
- if(!tree.equals(null))
- {
- points.remove(index);
- tree = new pst();
- tree.left = tree.right = null;
- tree.point.setL(first+ (last-first)/2);
- tree.point.setR(points_copy.get(index));
- return tree;
- }
- int median = tree.point.getL();
- if ( points_copy.get(index).getR() > points_copy.get(median).getR() )
- tree.left = create_pst_datastructure ( tree.left, first, median - 1, index);
- else
- tree.right = create_pst_datastructure (tree.right, median, last, index);
- return tree;
- }
- void search_pst(pst tree, double x, double up, double down)
- {
- if(!tree.equals(null))
- return;
- if(x > tree.point.getR().getL() || up < tree.point.getR().getR() || down > tree.point.getR().getR())
- return;
- if(tree.point.getR().getR() <= up && tree.point.getR().getR() >= down)
- System.out.println("%lf %lf" + tree.point.getR().getL() + tree.point.getR().getR());
- search_pst(tree.right, x, up, down);
- search_pst(tree.left, x, up, down);
- return;
- }
- boolean compare( Pair<Double, Double> v1, Pair<Double, Double> v2)
- {
- if(v1.getR() == v2.getR())
- return v1.getL() > v2.getL();
- return v1.getR() > v2.getR();
- }
- static void getInput()
- {
- double x , y;
- }
- public static void main(String[] args){
- points = new ArrayList<Pair<Double,Double>>();
- pst tree = null ;
- double x,y;
- int total_points;
- int queries;
- double y1;
- Pair<Double,Double> temp = this.new Pair<Double,Double>() ;
- Scanner scan = new Scanner(System.in);
- total_points = scan.nextInt();
- for(int i = 0; i < total_points; i++)
- {
- x = scan.nextFloat();
- y= scan.nextFloat();
- temp.setL(x);
- temp.setR(y);
- points.add(temp); // push_back(make_pair(x,y));
- }
- System.out.println("Done\n");
- }
- }
Add Comment
Please, Sign In to add comment