{"raw_statement":[{"iden":"statement","content":"*Non-maximum suppression (NMS)* has been widely used in several aspects of computer vision and is an integral part of many object detection algorithms. One of the most common problems in object detection is that an object might be detected multiple times. NMS technique ensures we get only a single detection per object.\n\nFor each class, a list of bounding boxes is proposed by the algorithm. Each box is associated with a score, indicating the confidence the algorithm thinks there is an object of the given class inside the box. Now let's see how the NMS procedure works. In the beginning, all the boxes are unselected and non-suppressed.\n\n \n\nIn this problem, we assume there is only one class, and simplify the object detection algorithm by only proposing *square shaped* boxes of the *same size*. Given the IoU threshold and a list of congruent square boxes proposed by the algorithm, can you report all selected boxes after going through the NMS procedure?\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.\n\nFor each test case, the first line contains two integers $n$, $S$ ($1 <= n <= 10^5$, $1 <= S <= 10^7$) and a floating-point number $t h r e s h o l d$ ($0. 300 <= t h r e s h o l d <= 0. 700$), indicating the number of square bounding boxes proposed by the detection algorithm, the size of the squares, and the IoU threshold. The $t h r e s h o l d$ is exact and is given to the third digit after the decimal point.\n\nIn the next $n$ lines, each line contains two integers $x$, $y$ ($0 <= x < x + S <= 10^7$, $0 <= y < y + S <= 10^7$) — the coordinates of the bottom left corner of a square box, followed by a floating point number $s c o r e$ ($0. 0 <= s c o r e <= 1. 0$) — the score of this box. Scores are exact and have at most six digits after the decimal point. Also, scores are distinct.\n\nFor each test case, the output starts with a line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1), and _y_ is the number of selected bounding boxes after going through the NMS procedure. The next line contains _y_ integers indicating the indices of the boxes (starting from 1) in *ascending* order.\n\nThere are $3$ boxes in the example: $[ 0, 4 ] times [ 0, 4 ]$, $[ 1, 5 ] times [ 1, 5 ]$ and $[ 2, 6 ] times [ 2, 6 ]$, which are already in descending order of score. The second box is suppressed because the IoU of the first and the second box is $frac(9, 23)$, which is strictly larger than $0. 390$, the IoU threshold. The third box is selected because the IoU of the first and the third box is $frac(1, 7)$, which is smaller than the IoU threshold.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.For each test case, the first line contains two integers $n$, $S$ ($1 <= n <= 10^5$, $1 <= S <= 10^7$) and a floating-point number $t h r e s h o l d$ ($0. 300 <= t h r e s h o l d <= 0. 700$), indicating the number of square bounding boxes proposed by the detection algorithm, the size of the squares, and the IoU threshold. The $t h r e s h o l d$ is exact and is given to the third digit after the decimal point.In the next $n$ lines, each line contains two integers $x$, $y$ ($0 <= x < x + S <= 10^7$, $0 <= y < y + S <= 10^7$) — the coordinates of the bottom left corner of a square box, followed by a floating point number $s c o r e$ ($0. 0 <= s c o r e <= 1. 0$) — the score of this box. Scores are exact and have at most six digits after the decimal point. Also, scores are distinct."},{"iden":"output","content":"For each test case, the output starts with a line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1), and _y_ is the number of selected bounding boxes after going through the NMS procedure. The next line contains _y_ integers indicating the indices of the boxes (starting from 1) in *ascending* order."},{"iden":"note","content":"There are $3$ boxes in the example: $[ 0, 4 ] times [ 0, 4 ]$, $[ 1, 5 ] times [ 1, 5 ]$ and $[ 2, 6 ] times [ 2, 6 ]$, which are already in descending order of score. The second box is suppressed because the IoU of the first and the second box is $frac(9, 23)$, which is strictly larger than $0. 390$, the IoU threshold. The third box is selected because the IoU of the first and the third box is $frac(1, 7)$, which is smaller than the IoU threshold."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n \\in \\mathbb{Z} $ be the number of square bounding boxes.  \n- Let $ S \\in \\mathbb{Z} $ be the side length of each square box.  \n- Let $ \\theta \\in \\mathbb{R} $ be the IoU threshold, with $ 0.300 \\leq \\theta \\leq 0.700 $.  \n- Let $ B_k = \\{ (x_i, y_i, s_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of boxes, where:  \n  - $ (x_i, y_i) \\in \\mathbb{Z}^2 $ is the bottom-left corner of box $ i $,  \n  - $ s_i \\in \\mathbb{R} $ is its distinct score, with $ 0.0 < s_i < 1.0 $.  \n\nEach box $ i $ corresponds to the square region $ [x_i, x_i + S] \\times [y_i, y_i + S] $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10 $  \n2. $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq S \\leq 10^7 $  \n3. $ 0 \\leq x_i < x_i + S < 10^7 $, $ 0 \\leq y_i < y_i + S < 10^7 $  \n4. $ 0.300 \\leq \\theta \\leq 0.700 $, with $ \\theta $ given to 3 decimal places  \n5. All scores $ s_i $ are distinct and given with at most 6 decimal places  \n\n**Objective**  \nApply Non-Maximum Suppression (NMS) as follows:  \n1. Sort boxes in descending order of score: $ s_{\\sigma(1)} > s_{\\sigma(2)} > \\dots > s_{\\sigma(n)} $, where $ \\sigma $ is a permutation of $ \\{1, \\dots, n\\} $.  \n2. Initialize an empty set $ \\mathcal{S} $ of selected boxes.  \n3. For each box $ i $ in sorted order:  \n   - If no box in $ \\mathcal{S} $ has IoU $ \\geq \\theta $ with box $ i $, add $ i $ to $ \\mathcal{S} $.  \n4. Output the indices (1-based) of boxes in $ \\mathcal{S} $ in ascending order.  \n\n**IoU Definition**  \nFor two axis-aligned squares $ i $ and $ j $:  \n$$\n\\text{IoU}(i, j) = \\frac{\\text{Area}(B_i \\cap B_j)}{\\text{Area}(B_i \\cup B_j)} = \\frac{\\text{Area}(B_i \\cap B_j)}{2S^2 - \\text{Area}(B_i \\cap B_j)}\n$$  \nwhere $ \\text{Area}(B_i \\cap B_j) = \\max(0, S - |x_i - x_j|) \\cdot \\max(0, S - |y_i - y_j|) $.","simple_statement":"Given a list of square boxes with scores, remove overlapping boxes using NMS: keep the highest-scored box, and suppress any box with IoU above a threshold. Output the indices (1-based) of remaining boxes in ascending order.","has_page_source":false}