Sam Brown
October 12, 2015 · Public |

HELP ME PLEASE WITH JAVA CODE

2D Range Searching

Suppose that you are given a set of two-dimensional points (x, y), whose coordinates are all non-negative integers such that 0 ≤ x, y ≤ 100000. Moreover, the number of points is also at most 100000.

The target of this question is to find all points lying inside a query range [ax, bx] × [ay, by], where the coordinates are all non-negative integers. One requirement in your implementation is that when you are searching for each of the specific numbers for the query range, say ax, bx, ay, and by, in your corresponding data structure, you need to use binary search. The purpose of doing this is to increase the efficiency of your program.

The input file name should be called “input.txt”. The first line in the input contains one number n, which is the number of two-dimensional points in the input file. Following this line, there are n lines, each of which contains a coordinate of the format (x, y). The last line contain the range query, which is given in the format of [ax,bx],[ay,by], which means the query range is [ax,bx]×[ay,by].

One more requirement in your implementation is that if the given number of points in your input is n, then in your program, you are required to use a 2D-array of size AT MOST n × n. Certainly, if you could manage to use a 2D-array of size smaller than n × n, it would be even better as long as you could accomplish the requested task in this assignment.

The output file name should be called “output.txt”. The first line in the output contains one number m, which is the number of input points falling in the query range [ax,bx]×[ay,by]. Following this line, there are m lines, each of which contains a coordinate of the format (x,y), (which lies in the query range). In the following, we provide a sample of the input and output files.

Sample input file: input.txt

29

(1, 2)

(1, 9)

(2, 1)

(2, 5)

(2, 10)

(2, 12)

(5, 1)

(5, 3)

(5, 9)

1

(5, 11)

(5, 19)

(6, 2)

(6, 5)

(6, 8)

(6, 10)

(6, 16)

(6, 18)

(11, 2)

(11, 3)

(11, 4)

(11, 9)

(11, 13)

(11, 15)

(11, 25)

(16, 5)

(16, 17)

(16, 18)

(22, 5)

(100000, 100000)

[2,9], [3,11]

Sample output file: output.txt

8

(2, 5)

(2, 10)

(5, 3)

(5, 9)

(5, 11)

(6, 5)

(6, 8)

(6, 10)