题目分析

这道题要求我们对一个给定的凸包（所有点都在凸包上，且原点在内部），进行多次区间查询：每次取出标号在区间 $[l,r]$ 中的点，求这些点构成的新凸包的面积的两倍（四舍五入到整数）。

由于原序列的点是凸包上的点（但输入顺序不一定是按极角排序），需要先转化为极角排序，然后问题就转化为：在环形凸包上取一段连续点（极角序连续），求其凸包面积。

关键观察

1. 凸包性质：所有点都在原凸包上，所以任意区间的点集的凸包就是这些点按极角序连接而成的多边形（区间点集的凸包就是区间点本身按极角序连接）。

2. 面积计算：给定多边形顶点 $P_1, P_2, ..., P_k$（按逆时针顺序），其面积的两倍可以用叉积公式：

   $$2S = \left|\sum_{i=1}^{k-1} (x_i y_{i+1} - x_{i+1} y_i) + (x_k y_1 - x_1 y_k)\right| $$

   由于原点在凸包内部，且点按逆时针排列，这个和一定为正。

3. 环形处理：因为凸包是环形的，区间 $[l,r]$ 可能跨越 $n$ 到 $1$ 的边界。处理方法是：将点序列复制一倍（$P_{n+i} = P_i$），然后在长度为 $2n$ 的序列上查询区间 $[l, r]$（若 $l \le r$ 则直接查；若 $l > r$ 则查 $[l, r+n]$）。

4. 快速查询：需要快速计算任意区间点构成的凸包面积（即区间叉积和）。这可以用前缀和实现。

算法步骤

1. 极角排序：将输入点按相对于原点的极角排序（用 atan2 或叉积比较）。

   • 注意：原点在凸包内部，所以所有点不会集中在半平面内。
   • 排序后得到逆时针顺序的点序列 $Q_1, Q_2, ..., Q_n$。

2. 前缀和预处理：

   • 计算叉积前缀和：$$\text{pref}[i] = \sum_{j=1}^{i-1} (Q_j \times Q_{j+1}), \quad \text{其中 } Q_a \times Q_b = x_a y_b - x_b y_a $$
   • 同时存储 $Q_{n+1} = Q_1$，以处理环形。
   • 将序列复制一倍：$Q_{n+i} = Q_i$，并计算长度为 $2n$ 的前缀和。

3. 查询处理：

   • 对每个查询 $[l, r]$（$1 \le l,r \le n$）：
     • 如果 $l \le r$：实际区间长度为 $len = r-l+1$，对应排序后序列的区间 $[pos_l, pos_r]$。
     • 如果 $l > r$：实际区间包含 $l \sim n$ 和 $1 \sim r$，对应排序后序列的区间 $[pos_l, pos_r + n]$。
   • 设排序后的位置数组为 id[]，其中 id[i] 表示原标号 $i$ 的点在极角序中的位置（$1 \le id[i] \le n$）。
   • 则查询对应的极角序区间为 $[L, R]$（在长度为 $2n$ 的序列上），其中：
     • $L = id[l]$
     • $R = id[r] + (l \le r ? 0 : n)$
   • 注意：如果 $L > R$，交换 $L$ 和 $R$。
   • 然后计算面积的两倍：$$\text{area} = \text{pref}[R] - \text{pref}[L] + (Q_R \times Q_L) $$最后取绝对值，再四舍五入输出（由于都是整数运算，等价于判断奇偶性调整）。

4. 四舍五入处理：

   • 因为面积的两倍 $2S$ 可能是整数或半整数。
   • 令 $val = \text{area}$（叉积和），则实际 $2S = |val|$。
   • 四舍五入到整数：如果 $|val|$ 是偶数，直接输出 $|val|$；如果是奇数，输出 $|val|$（因为 .5 会进位）。

复杂度分析

• 极角排序：$O(n \log n)$
• 前缀和预处理：$O(n)$
• 每个查询：$O(1)$
• 总复杂度：$O((n+m) \log n)$

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Point {
    ll x, y;
    Point() {}
    Point(ll x, ll y) : x(x), y(y) {}
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    bool operator<(const Point& p) const {
        // 按极角排序
        bool up1 = y > 0 || (y == 0 && x > 0);
        bool up2 = p.y > 0 || (p.y == 0 && p.x > 0);
        if (up1 != up2) return up1 > up2;
        return x * p.y - y * p.x > 0;
    }
};

ll cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<Point> orig(n + 1); // 原标号从1开始
    for (int i = 1; i <= n; i++) {
        cin >> orig[i].x >> orig[i].y;
    }
    
    // 极角排序
    vector<int> id(n + 1); // id[i]: 原标号i的点在极角序中的位置(1-based)
    vector<Point> sorted;
    for (int i = 1; i <= n; i++) {
        sorted.push_back(orig[i]);
    }
    sort(sorted.begin(), sorted.end());
    
    // 建立原标号到极角序位置的映射
    map<pair<ll, ll>, int> mp;
    for (int i = 0; i < n; i++) {
        mp[{sorted[i].x, sorted[i].y}] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        id[i] = mp[{orig[i].x, orig[i].y}];
    }
    
    // 复制一倍处理环形
    vector<Point> p(2 * n + 2);
    for (int i = 1; i <= n; i++) {
        p[i] = sorted[i - 1];
        p[i + n] = sorted[i - 1];
    }
    
    // 计算叉积前缀和
    vector<ll> pref(2 * n + 2, 0);
    for (int i = 1; i <= 2 * n; i++) {
        int j = (i % (2 * n)) + 1;
        pref[i] = (i > 1 ? pref[i - 1] : 0) + cross(p[i], p[j]);
    }
    
    // 处理查询
    while (m--) {
        int l, r;
        cin >> l >> r;
        
        int L = id[l], R = id[r];
        if (l <= r) {
            // 区间不跨过n
            if (L > R) swap(L, R);
            // 现在L <= R
            ll area = pref[R - 1] - pref[L - 1] + cross(p[R], p[L]);
            area = llabs(area);
            // 四舍五入：因为area是2倍面积，如果area是奇数则说明有0.5
            if (area % 2 == 1) area++; // 奇数时+0.5相当于进1
            cout << area << '\n';
        } else {
            // 区间跨过n：相当于[L, R+n]
            R += n;
            if (L > R) swap(L, R);
            ll area = pref[R - 1] - pref[L - 1] + cross(p[R], p[L]);
            area = llabs(area);
            if (area % 2 == 1) area++;
            cout << area << '\n';
        }
    }
    
    return 0;
}

注意事项

1. 极角排序时要注意处理坐标轴上的点（本题保证原点在内部，不会出现共线情况）。
2. 叉积可能很大，要用 long long。
3. 四舍五入处理：因为 $2S$ 是整数或半整数，当 $2S$ 为奇数时，实际面积 $S$ 有 $0.5$ 的小数部分，需要进位。
4. 由于点都是整数坐标，叉积和也是整数，所以 $2S$ 是整数。