fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Ideone{ 
  5. 	public static void main(String[] args)throws java.lang.Exception{
  6. 		new Ideone().run();
  7. 	}
  8.  
  9. 	void run(){
  10. 		Scanner in = new Scanner(System.in);
  11. 		int numQueries = in.nextInt();
  12. 		Point2D root = null;
  13. 		for(int i=0; i<numQueries; i++){
  14. 			int type = in.nextInt();
  15. 			if(type == 0){   // Add a point
  16. 				double x = in.nextDouble();
  17. 				double y = in.nextDouble();
  18. 				root = addPoint(root, x, y, true);
  19. 			}else{
  20. 				double x1  = in.nextDouble();
  21. 				double y1 = in.nextDouble();
  22. 				double x2  = in.nextDouble();
  23. 				double y2 = in.nextDouble();
  24. 				System.out.println("the points in between the rectange with end points " + 
  25. 				     new Point2D(x1, y1) + " and " + new Point2D(x2, y2) + " are :");
  26. 				printPointsInRange(root, x1, y1, x2, y2, true);
  27. 			}
  28. 		}
  29. 	}
  30.  
  31.  
  32. 	// prints all points in the rectangle which has top left coordinates
  33. 	// (x1, y1) and bottom right coordinates (x2, y2)
  34. 	void printPointsInRange(Point2D root,
  35. 						double x1, double y1, 
  36. 						double x2, double y2, boolean vertical){
  37. 		if(root==null){
  38. 			return;
  39. 		}
  40. 		double x = root.x;
  41. 		double y = root.y;
  42. 		boolean outsideRange = Double.compare(x, x1)<0 || 
  43. 								Double.compare(x, x2)>0 ||
  44. 								 Double.compare(y, y1)>0 || 
  45. 								 Double.compare(y, y2)<0;
  46. 		if(!outsideRange){
  47. 			System.out.println(root);
  48. 		}
  49.  
  50. 		if(vertical){
  51. 			if(Double.compare(x, x1)<=0){ 
  52. 				// root lies left of left boundary or on the boundary
  53. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  54. 			}else if(Double.compare(x, x2)>0){
  55. 				// root lies right of right boundary
  56. 				printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
  57. 			}else if(Double.compare(x, x2)==0){
  58. 				// root lies on right boundary
  59. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  60. 			}else{
  61. 				// root lies in between x1 and x2
  62. 				printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
  63. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  64. 			}
  65. 		}else{
  66. 			if(Double.compare(y, y2)<=0){ 
  67. 				// root lies below bottom boundary or on bottom boundary
  68. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  69. 			}else if(Double.compare(y, y1)>0){
  70. 				// root lies above top boundary
  71. 				printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
  72. 			}else if(Double.compare(y, y1)==0){
  73. 				// root lies on top boundary
  74. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  75. 			}else{
  76. 				// root lies in between y1 and y2
  77. 				printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
  78. 				printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
  79. 			}
  80. 		}
  81. 	}
  82.  
  83. 	Point2D addPoint(Point2D root, double x, double y, boolean vertical){
  84. 		if(root==null){
  85. 			return new Point2D(x, y);
  86. 		}
  87. 		if(vertical){   // vertical division
  88. 			double compare = Double.compare(root.x, x);
  89. 			if(compare<0){ // point is on left of root
  90. 				root.left = addPoint(root.left, x, y, !vertical);
  91. 			}else{        // point is on right of root or on root's x
  92. 				root.right = addPoint(root.right, x, y, !vertical);
  93. 			}
  94. 		}else{
  95. 			double compare = Double.compare(y, root.y);
  96. 			if(compare>0){    // point is above the root
  97. 				root.right = addPoint(root.right, x, y, !vertical);
  98. 			}else{            // point is below the root or on root's y 
  99. 				root.left = addPoint(root.left, x, y, !vertical);
  100. 			} 
  101. 		}
  102. 		return root;
  103. 	}
  104. }
  105.  
  106. class Point2D{
  107. 	double x;
  108. 	double y;
  109. 	Point2D right;
  110. 	Point2D left;
  111. 	public Point2D(double x, double y){
  112. 		this.x = x;
  113. 		this.y = y;
  114. 		right = left = null;
  115. 	}
  116.  
  117. 	public String toString(){
  118. 		return "( " + x + ", " + y + " )";
  119. 	}
  120. }
Success #stdin #stdout 0.12s 380672KB
comments (?)
stdin
copy 
5
0 .7 .2
1 .5 .5 1 0
0 .5 .4
0 1.4 0
1 .5 .5 1 0
stdout
copy 
the points in between the rectange with end points ( 0.5, 0.5 ) and ( 1.0, 0.0 ) are :
( 0.7, 0.2 )
the points in between the rectange with end points ( 0.5, 0.5 ) and ( 1.0, 0.0 ) are :
( 0.7, 0.2 )
( 0.5, 0.4 )
https://ideone.com/IMEPCs
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!