HDU 5032 Always Cook Mushroom：離線極角排序 + BIT 解二維平面區域和查詢

問題描述

1000×1000 整數網格，點 (x,y) 權值 = (x+A)(y+B)。Q 次查詢：給定極角 θ（由向量 (a,b) 確定）和半徑 X，求極角 ≤ θ 且 x ≤ X 的所有點權值和。A,B 為常數。

離線處理思路

1. 將所有網格點 (1..1000, 1..1000) 按極角 atan2(y,x)（或斜率 y/x）排序，存入數組 points。
2. 每個查詢包含 (X, θ, id)，按 θ 排序。
3. 雙指針掃描：遍歷查詢，將 points 中極角 ≤ 當前查詢 θ 的點依次加入 BIT（按 y 座標為索引，值為權值）。
4. 查詢 BIT 前綴和 query(X) 即為答案。

BIT 實現

ll bit[1005];
void add(int idx, ll val) { for (; idx<=1000; idx+=idx&-idx) bit[idx]+=val; }
ll sum(int idx) { ll r=0; for(; idx>0; idx-=idx&-idx) r+=bit[idx]; return r; }

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Pt { int x, y; double ang; };
struct Qry { int X, id; double ang; ll ans; };
vector pts;
vector qrs;
ll bit[1005];

int main() {
    // 預處理所有點
    for (int x=1; x<=1000; x++)
        for (int y=1; y<=1000; y++)
            pts.push_back({x, y, atan2(y, x)});
    sort(pts.begin(), pts.end(), [](Pt a, Pt b){ return a.ang < b.ang; });

    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        int A, B; scanf("%d%d", &A, &B);
        int Q; scanf("%d", &Q);
        qrs.resize(Q);
        for (int i=0; i