Detectors draw several boxes around each object. Non-maximum suppression keeps one.
What to build
A program that runs greedy non-maximum suppression.
Requirements
- Visit boxes from the highest score to the lowest (equal scores in input order). Keep a box if its IoU with every already-kept box is at most the threshold t; otherwise remove it.
- Print
kept: …with the kept indices (from 0) in the order they were kept, thenremoved: …with the removed indices in increasing order, orremoved: none.
Input
Line 1: N and t. Then N lines x1 y1 x2 y2 score.
Output
Two lines.
Constraints
1 ≤ N ≤ 200; 0 < t < 1.
Example
Input:
6 0.5
10 10 50 50 0.9
12 14 52 54 0.8
60 20 90 60 0.75
8 8 48 46 0.7
62 22 92 58 0.6
30 70 40 80 0.3
Output:
kept: 0 2 5
removed: 1 3 4
Why it works
The highest-scoring box is the most trusted guess for its object, and any box overlapping it heavily is probably the same object, so removing those leaves one box per object.
Examples
Example 1 · Input
6 0.5 10 10 50 50 0.9 12 14 52 54 0.8 60 20 90 60 0.75 8 8 48 46 0.7 62 22 92 58 0.6 30 70 40 80 0.3
Expected output
kept: 0 2 5 removed: 1 3 4
Example 2 · Input
3 0.3 0 0 10 10 0.2 1 1 11 11 0.9 50 50 60 60 0.5
Expected output
kept: 1 2 removed: 0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the indices by score from high to low, keeping the input order for equal scores (Python's `sorted` is stable).
Hint 2
Keep a box when its IoU with every box kept so far is at most the threshold.
Solution
Show one correct solution (try it yourself first)
def iou(a, b):
w = max(0.0, min(a[2], b[2]) - max(a[0], b[0]))
h = max(0.0, min(a[3], b[3]) - max(a[1], b[1]))
inter = w * h
return inter / ((a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - inter)
n, t = input().split()
n, t = int(n), float(t)
boxes, scores = [], []
for _ in range(n):
v = list(map(float, input().split()))
boxes.append(v[:4])
scores.append(v[4])
order = sorted(range(n), key=lambda i: -scores[i])
kept = []
for i in order:
if all(iou(boxes[i], boxes[j]) <= t for j in kept):
kept.append(i)
removed = sorted(i for i in range(n) if i not in kept)
print("kept: " + " ".join(map(str, kept)))
print("removed: " + (" ".join(map(str, removed)) if removed else "none"))