题目理解

我们有一个平面图，被划分为若干个开发区域（面）。每个开发区域的矿量等于其面积的平方。

现在有 $k$ 个开采计划，每个计划指定一个多边形区域（由若干开发区域组成），我们需要计算：

$$\text{优先度} = \frac{\sum \text{矿量}}{\sum \text{面积}} = \frac{\sum s_i^2}{\sum s_i} $$

其中 $s_i$ 是每个开发区域的面积。

关键难点：

1. 输入是平面图（点和边），需要重建面信息
2. 开采计划的多边形边界是加密的，需要实时解密
3. 需要高效计算多边形区域内的开发区域

问题分析

平面图性质

根据平面图欧拉公式：$V - E + F = 1 + C$（其中 $C$ 是连通分量数）

对于连通平面图：$E \leq 3V - 6$，题目保证 $m \leq 3n-6$。

核心思路：平面图转对偶图

这是解决此类平面图区域查询问题的标准方法：

1. 建立对偶图：

   • 原平面图中的每个面对应对偶图中的一个节点
   • 原图中的每条边对应对偶图中的一条边

2. 面信息预处理：

   • 计算每个面的面积（用叉积）
   • 计算每个面的矿量（面积平方）

3. 生成树构造：

   • 在对偶图中构造生成树，用于快速判断包含关系

解法思路

方法：平面图转对偶图 + 生成树

算法流程：

步骤1：预处理平面图

struct Point {
    long long x, y;
    Point operator - (const Point &b) const {
        return {x - b.x, y - b.y};
    }
    long long cross(const Point &b) const {
        return x * b.y - y * b.x;
    }
} p[N];

struct Edge {
    int u, v, id;
    double angle;  // 极角，用于排序
    bool operator < (const Edge &b) const {
        return angle < b.angle;
    }
};

步骤2：建立对偶图

// 对每个点的出边按极角排序
vector<Edge> edges;
vector<int> G[N];  // 原图的邻接表
vector<int> dual_edges;  // 对偶图的边

// 通过旋转卡壳法找到面
void build_dual_graph() {
    // 对每个点的出边按极角排序
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end(), [&](int a, int b) {
            return edges[a].angle < edges[b].angle;
        });
    }
    
    // 遍历所有边，找到所有面
    vector<bool> visited(edges.size(), false);
    for (int i = 0; i < edges.size(); i++) {
        if (visited[i]) continue;
        
        vector<int> face;
        long long area = 0;
        int cur = i;
        
        do {
            visited[cur] = true;
            face.push_back(cur);
            
            // 计算面积贡献
            area += p[edges[cur].u].cross(p[edges[cur].v]);
            
            // 找到下一条边（在当前终点的出边中，当前边的反向边的下一条）
            int u = edges[cur].v;
            auto &adj = G[u];
            auto it = lower_bound(adj.begin(), adj.end(), edges[cur^1].id, 
                                [&](int a, int b) { return edges[a].angle < edges[b].angle; });
            if (++it == adj.end()) it = adj.begin();
            cur = *it;
            
        } while (cur != i);
        
        // 记录面信息
        if (area > 0) {  // 外面面积是负的
            faces.push_back({area, face});
        }
    }
}

步骤3：建立生成树

在对偶图中建立生成树，根节点为无穷远面对应的节点：

struct DualNode {
    long long area, sq_area;  // 面积和面积平方
    int parent;
    vector<int> children;
} dual[N];

void build_spanning_tree() {
    // 以无穷远面为根
    // 通过BFS或DFS建立生成树
    // 同时计算子树和
}

步骤4：处理查询

对于每个多边形查询：

1. 解密边界点
2. 计算多边形与各个面的交并关系
3. 利用生成树信息快速求和

// 计算多边形内的总面积和总矿量
pair<long long, long long> query_polygon(const vector<int> &points) {
    long long total_area = 0, total_sq = 0;
    
    // 计算多边形面积（用于判断方向）
    long long poly_area = 0;
    for (int i = 0; i < points.size(); i++) {
        int j = (i + 1) % points.size();
        poly_area += p[points[i]].cross(p[points[j]]);
    }
    
    // 判断每个面是否在多边形内
    for (int i = 0; i < faces.size(); i++) {
        if (is_face_inside_polygon(i, points, poly_area > 0)) {
            total_area += faces[i].area;
            total_sq += faces[i].sq_area;
        }
    }
    
    return {total_sq, total_area};
}

关键优化：生成树技巧

利用生成树，我们可以 $O(1)$ 判断一个面是否在查询多边形内：

1. 对每个面，记录其到根的路径上的关键边
2. 查询时，只需检查多边形与这些关键边的相交情况
3. 使用扫描线 + 平衡树维护当前穿过的边

算法复杂度分析

• 预处理：
  • 建立对偶图：$O(m \log m)$（排序）
  • 建立生成树：$O(m)$
• 每次查询：$O(d + \log m)$，其中 $d$ 是多边形边数
• 总复杂度：$O(m \log m + \sum d)$

关键技巧总结

1. 平面图转对偶图：核心思想，将区域查询转化为图遍历
2. 极角排序：用于确定面的边界
3. 生成树优化：快速判断包含关系
4. 分数化简：使用gcd保证最简形式
5. 实时解密：按题目要求处理加密输入

这种方法充分利用了平面图的性质，通过对偶图将复杂的几何问题转化为图论问题，从而实现了高效查询。