[L. Dynamic Convex Hull ]( Problem - L - Codeforces ) 题解
预处理原凸包面积，枚举新点 对原凸包画切线，将两个切点和新点重建新凸包，求和新凸包中的面积贡献。
新凸包是有原有凸包与新点构成的凸包合并而来的，所以新凸包中的面积会有原凸包中的面积贡献，所以需要预处理优化。
具体看代码注释，博主懒~，所以注释交给deep seek加的，如有问题评论或私信~
#include <bits/stdc++.h>
using namespace std;
//-------------------------------------------------------------------------------------------
#define int long long
#define lost_R ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define P pair<int, int>
#define lowbit(x) (x & (-x))
#define dbg1(x) cout << "# " << x << endl
#define dbg2(x, y) cout << "# " << x << " " << y << endl
#define endl '\n'
const int mod = 998244353;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-9;
//--------------------------------------------------------------------------------------
int n, m;
struct Point {int x, y;int id; // 点的标识，用于区分原始点和查询点Point(int x = 0, int y = 0,int id = 0) : x(x), y(y), id(id) {}bool operator<(const Point &p) const { return x < p.x || (x == p.x && y < p.y); }
};typedef Point Vector;// 向量运算
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double k) { return Vector(A.x * k, A.y * k); }// 叉积
int Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }// 符号函数
int Sign(int x) {return x > 0 ? 1 : (x<0?-1:0);
}vector<Point> a; // 存储凸包点集
vector<int> sum; // 前缀和数组，用于快速计算面积// 判断三点是否左转（逆时针）
int turn_left(Point u, Point v, Point w) {return Sign(Cross(v - u, w - u));
}// 二分查找切点
int search(auto f) {int l = 0, r = (int)a.size() - 1;if (f(a[0], a.back())) {while (l + 1 < r) {int mid = (l + r) / 2;if (f(a[mid], a[l]) && f(a[mid], a[mid - 1])) l = mid;else r = mid;}return l;} else {while (l + 1 < r) {int mid = (l + r) / 2;if (f(a[mid], a[r]) && f(a[mid], a[mid + 1])) r = mid;else l = mid;}return r;}
}// 获取点u的两条切线
vector<Point> get_tan(Point u) {return {a[search([&](auto x, auto y) { return turn_left(u, y, x) > 0; })],a[search([&](auto x, auto y) { return turn_left(u, x, y) > 0; })]};
}// 使用Andrew算法构建凸包
vector<Point> build_convex_hull(vector<Point>& points) {sort(points.begin(), points.end());vector<Point> hull;// 构建下凸包for (int i = 0; i < points.size(); i++) {while (hull.size() >= 2 && turn_left(hull[hull.size()-2], hull.back(), points[i]) <= 0) {hull.pop_back();}hull.push_back(points[i]);}// 构建上凸包int lower_size = hull.size();for (int i = points.size()-2; i >= 0; i--) {while (hull.size() > lower_size && turn_left(hull[hull.size()-2], hull.back(), points[i]) <= 0) {hull.pop_back();}hull.push_back(points[i]);}// 移除重复的起点if (hull.size() > 1) hull.pop_back();return hull;
}// 计算多边形面积的2倍
int area2(const vector<Point> &p) {int res = 0;for (int i = 0; i < p.size(); i++) {int j = (i + 1) % p.size();res += Cross(p[i], p[j]);}return abs(res);
}// 判断点u是否在凸包内部
bool inside(Point &u) {if (a.size() < 3) return false; // 不是严格凸包// 二分查找所在的三角形扇区int l = 1, r = a.size() - 2;while (l < r) {int mid = (l + r + 1) >> 1;if (turn_left(a[0], a[mid], u) >= 0) l = mid;else r = mid - 1;}// 检查是否在三角形内return turn_left(a[0], a[l], u) >= 0 &&turn_left(a[l], a[l+1], u) >= 0 &&turn_left(a[l+1], a[0], u) >= 0;
}// 计算从点l到点r的累计面积（顺时针方向）
int Sum(int l, int r) {if (l <= r) return sum[r] - sum[l];else return sum[a.size()] - sum[l] + sum[r];
}void solve() {a.clear();cin >> n;for (int i = 0; i < n; i++) {int x,y;cin>>x>>y;a.push_back({x,y});// points[i].id = i; // 正数ID表示原始点}// 构建凸包a = build_convex_hull(a);n = a.size(); // 更新凸包点数for(int i=0;i<n;i++){a[i].id=i;}// 计算前缀和sum.resize(n + 1);sum[0] = 0;for (int i = 0; i < n; i++) {int j = (i + 1) % n;sum[i + 1] = sum[i] + Cross(a[i], a[j]);}cin >> m;while (m--) {int k;cin >> k;vector<Point> b;// 处理每个查询点for (int i = 1; i <= k; i++) {Point t;cin >> t.x >> t.y;t.id = -i; // 负数ID表示查询点// 如果点在凸包内部则忽略if (n >= 3 && inside(t)) continue;// 获取切线并加入集合auto tangent = get_tan(t);b.push_back(t);b.push_back(tangent[0]);b.push_back(tangent[1]);}if (b.empty()) {// 所有点都在凸包内部，直接输出凸包面积cout << sum[n] << endl;} else {// 构建新的凸包vector<Point> new_hull = build_convex_hull(b);int ans = 0;// 计算新凸包的面积贡献for (int i = 0; i < new_hull.size(); i++) {int j = (i + 1) % new_hull.size();if (new_hull[i].id < 0 || new_hull[j].id < 0) {// 连接的是查询点，直接计算叉积ans += Cross(new_hull[i], new_hull[j]);} else {// 连接的是原始凸包点，使用前缀和快速计算ans += Sum(new_hull[i].id, new_hull[j].id);}}cout << abs(ans) << endl;}}
}signed main() {lost_R;int T = 1;cin >> T;while (T--) solve();return 0;
}