Problem Description
Gug is drawing rectangles on a piece of paper, for some reason. Every rectangle that he draws has a certain height H and a certain width W.
Oddly enough, he considers the variation between two different rectangles as min(|Ha - Hb|, |Wa - Wb|), if the first rectangle is of dimensions Ha x Wa and the second rectangle is of dimensions Hb x Wb.
Gug starts off with an empty piece of paper, and he can, at any time, draw a new rectangle or remove an existing rectangle from the piece of paper. It is guaranteed that no two rectangles on the piece of paper at one time will have the exact same dimensions.
To test you, he also can show you a new rectangle, and ask you to find the rectangle on his piece of paper which it is most similar to (least variation). He then wants you to tell him what is its variation to this new rectangle.
Implementation Details
This is a function call question. You are to implement these three functions:
void add_rectangle(int H, int W)
This function should add a rectangle with height H and width W. It is guaranteed that no existing rectangle with the same dimensions already exist on the piece of paper, and that the rectangle dimensions will be between 1 and 109 inclusive.
void erase_rectangle(int H, int W)
This function should remove a rectangle of height H and width W from the piece of paper. It is guaranteed that a rectangle with the exact dimensions exist on the piece of paper.
int test_rectangle(int H, int W)
This function should return the minimum variation between this new rectangle of height H and W and any rectangle currently on his piece of paper. It is guranteed that there is at least one rectangle on his piece of paper, and that the query dimensions are between 1 and 109 inclusive.
Under the Attachments tab, you are provided with a header file, sample grader, solution template, and a compile command. You are advised to test the solution locally before submission to the judge. A sample testcase simulating the sample interaction below is also included.
Limits
Subtask 1 (30%): Total number of calls ≤ 3000.
Subtask 2 (32%): Total number of calls ≤ 300000, erase_rectangle will not be called, all calls to test_rectangle will be done after all calls to add_rectangle.
Subtask 3 (38%): Total number of calls ≤ 300000.
Subtask 4 (0%): Sample Testcases.
Sample Interaction
add_rectangle(3, 5) is called.
add_rectangle(6, 9) is called.
test_rectangle(4, 11) is called. It should return
1.
test_rectangle(1, 3) is called. It should return
2.
erase_rectangle(3, 5) is called.
test_rectangle(4, 11) is called. It should return
2.