演算法題：星星在你的窗戶 — 矩形窗口最大亮度星星覆蓋問題

問題背景

這是一道經典的計算幾何 + 最大子矩陣和變體題目。給定平面上 N 顆星星（座標 x, y 及亮度 1~100），以及一個固定寬高 (W, H) 的軸平行矩形窗口。窗口可平移不可旋轉，邊界上的星星不計入。目標是找到窗口位置使內部星星亮度總和最大。

輸入輸出格式

• 多測試用例，每組第一行：n W H (1 ≤ n ≤ 10000, 1 ≤ W,H ≤ 1,000,000)
• 隨後 n 行：x y c (0 ≤ x,y < 2^31，無重疊座標)
• 輸出：每組一行，最大亮度和

核心思路：離散化 + 掃描線 + 線段樹/前綴和

1. 座標離散化：將所有星星的 x, y 坐標收集，排序去重，映射到 1..M。因為 n ≤ 10000，離散後座標數 ≤ 20000，可將大座標空間壓縮。
2. 二維前綴和：在離散網格上建立亮度矩陣 sum[i][j] 表示 (1,1) 到 (i,j) 矩形內亮度和。
3. 枚舉窗口：窗口在離散座標中對應寬高為 w_idx, h_idx 的子矩陣。利用前綴和 O(1) 計算任意窗口亮度和：
   val = sum[x+w][y+h] - sum[x][y+h] - sum[x+w][y] + sum[x][y]
4. 優化：直接雙重循環枚舉左上角可能位置，複雜度 O(M^2) 可能過大。改用掃描線：固定 y 範圍，用滑動窗口維護 x 方向最大和，降至 O(M^2) 或 O(N log N)。

樣例解析

輸入：
3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1

輸出：
5
6

第一組：窗口 (5,4) 覆蓋前兩顆星 (1,2) 和 (2,3) 亮度 3+2=5。
第二組：窗口移動覆蓋 (1,2),(2,3),(5,3) 亮度 3+2+1=6。

複雜度分析

• 離散化：O(N log N)
• 建立前綴和：O(M_x * M_y) ≤ O(N^2) 最壞 10^8 邊界，需優化
• 實際建議：使用 掃描線 + 線段樹維護區間最大值，將枚舉 y 區間，x 方向用滑動窗口或線段樹查詢最大和，總複雜度 O(N^2) 或 O(N log N) 視實現而定。

提示：座標範圍極大 (2^31) 必須離散化；星星數 10000 允許 O(N^2) 邊界算法在 C++ 中通過，Python 需更優化。