Approach
Sorting and greedy selection
For ABC075 D — Axis-Parallel Rectangle, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 46 lines of Python from the credited upstream file abc075_d.py.
- The implementation visibly relies on ordered lookup.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def main():5 import sys6 7 input = sys.stdin.readline8 9 n, k = map(int, input().split())10 x = [0 for _ in range(n)]11 y = [0 for _ in range(n)]12 13 for i in range(n):14 xi, yi = map(int, input().split())15 x[i] = xi16 y[i] = yi17 18 sx = sorted(x)19 sy = sorted(y)20 21 ans = float("inf")22 23 for xi in range(n):24 for xj in range(xi + 1, n):25 for yi in range(n):26 for yj in range(yi + 1, n):27 count = 028 29 x_min = sx[xi]30 x_max = sx[xj]31 y_min = sy[yi]32 y_max = sy[yj]33 34 for p in range(n):35 if x_min <= x[p] <= x_max and y_min <= y[p] <= y_max:36 count += 137 38 if count >= k:39 ans = min(ans, (x_max - x_min) * (y_max - y_min))40 41 print(ans)42 43 44if __name__ == "__main__":45 main()46