ARNAB4 - Insert and Window Query

Professor Arnab is hiding some gold coins in a field. Students are required to find the gold coins. Since the professor is very busy person, he assigns you the task of hiding the coins. Since, you are a student, you will help your friends by telling them the coordinates of the points within a rectangular range where coins are present.

Formally, you will be given 2 types of queries : Insert (0) and Range Search (4). The field is in X-Y plane. Each point (x, y) is such that 0.0 <= x, y <= 1.0. The coordinates (x, y) will be such that both x and y have at most 6 digits after the decimal. For Range Search, the ranges will be rectangular and the sides of the rectangle will be parallel to the axes. You will be given the coordinates of bottom-left point and top-right point. You have to report all the points with the rectangular range (including boundaries). You need to print it in increasing x , for ties : print it in increasing y. Output only distinct points.

Note: Output exactly 6 digits after decimal

Input:
0 x y : Insert a coin at (x, y)
4 x1 y1 x2 y2 : Report all the points in the given rectangular range, with (x1, y1) as bottom-left point and (x2, y2) as top-right point.

Output:
For every query, print the query statement as it is.
For Range Search query, print all the points in the range.
For every query, print a blank line at the end

Constraints:

All values <= 1

Total Queries <= 1e5

Sample Input

0 0.5 0.5
0 0.1 0.2
4 0.4 0.4 0.6 0.6
4 0.1 0.1 0.7 0.7

Sample Output


0 0.500000 0.500000

0 0.100000 0.200000

4 0.400000 0.400000 0.600000 0.600000
0.500000 0.500000

4 0.100000 0.100000 0.700000 0.700000
0.100000 0.200000
0.500000 0.500000

 

Credits : Saurav Kumar for the story.

As this is tutorial problem, try solving it using kdtrees and quadtrees


Added by:devu
Date:2015-01-22
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2016-12-13 04:05:06 Fendy
Hi I got SIGXFSZ when running the solution is it because my output file reached the limit? Please clarify this, thank you :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.