题目分析

有一个由上下镜面组成的通道，中间有圆形和矩形的光学元件。光线从通道下方射入，需要找到至少移除多少个元件，使得存在一条光线路径能从通道上方射出。

关键观察：如果元件之间相互接触（相交或相切），就会阻挡光线通过。我们需要找到最少的元件移除数量，使得剩下的元件不会形成从下到上的连通阻挡。

解题思路

核心思想

将问题建模为网络流最小割问题：

• 每个元件视为图中的节点
• 元件间的相交关系视为图中的边
• 接触上边界的元件连接源点
• 接触下边界的元件连接汇点
• 最小割即为需要移除的最少元件数

关键技术

• 节点拆分：处理点容量约束
• 几何相交检测：判断圆形、矩形间的相交关系
• Dinic算法：高效求解最大流/最小割

算法步骤

1. 读入数据并分类存储元件
2. 构建网络流图：节点拆分处理点容量
3. 几何相交检测：建立元件间的连接关系
4. 连接边界元件：源点连接上边界，下边界连接汇点
5. 运行最大流算法：计算最小割

完整代码

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;

const int N = 305;
const int M = 1e6 + 5;
const int inf = 2e9 + 5;
const double eps = 1e-6;

int n, Cx, Cy;  // 通道尺寸
int circle_cnt = 0, rect_cnt = 0;  // 圆形和矩形元件计数

// 圆形元件结构
struct Circle {
    int x, y, r, id;
} circles[N];

// 矩形元件结构  
struct Rectangle {
    int x, y, X, Y, id;  // 左下角(x,y), 右上角(X,Y)
} rects[N];

// 计算几何工具类
class GeometryUtils {
public:
    // 计算两点间距离
    inline double dist(int x1, int y1, int x2, int y2) {
        return sqrt(sq(x1 - x2) + sq(y1 - y2));
    }
    
    // 计算整数的平方
    inline double sq(int x) {
        return 1.0 * x * x;
    }
    
    // 符号函数，用于浮点数比较
    inline int sign(double x) {
        return (fabs(x) < eps ? 0 : (x > 0 ? 1 : -1));
    }
    
    // 判断点是否在线段范围内
    inline bool point_in_segment(int x, int y_min, int y_max, int y, int x_min, int x_max) {
        return x_min <= x && x <= x_max && y_min <= y && y <= y_max;
    }
    
    // 判断圆形是否接触上边界
    inline bool circle_touches_top(int i) {
        // 圆心到上边界的垂直距离 <= 半径
        bool vertical_contact = (Cy - circles[i].y) <= circles[i].r;
        // 圆心在通道宽度范围内，且到上边界某点的水平距离 <= 半径
        bool horizontal_contact = dist_to_top_segment(circles[i].x, circles[i].y) <= circles[i].r;
        return vertical_contact && horizontal_contact;
    }
    
    // 判断圆形是否接触下边界
    inline bool circle_touches_bottom(int i) {
        // 圆心到下边界的垂直距离 <= 半径
        bool vertical_contact = circles[i].y - circles[i].r <= 0;
        // 圆心在通道宽度范围内，且到下边界某点的水平距离 <= 半径
        bool horizontal_contact = dist_to_bottom_segment(circles[i].x, circles[i].y) <= circles[i].r;
        return vertical_contact && horizontal_contact;
    }
    
    // 判断矩形是否接触上边界
    inline bool rect_touches_top(int i) {
        return rects[i].Y >= Cy && rects[i].x <= Cx && rects[i].X >= 0;
    }
    
    // 判断矩形是否接触下边界
    inline bool rect_touches_bottom(int i) {
        return rects[i].y <= 0 && rects[i].x <= Cx && rects[i].X >= 0;
    }
    
    // 计算点到上边界线段的最短距离
    double dist_to_top_segment(int x, int y) {
        if (0 <= x && x <= Cx) {
            return abs(Cy - y);  // 垂直距离
        } else if (x < 0) {
            return dist(0, Cy, x, y);  // 到左端点距离
        } else {
            return dist(Cx, Cy, x, y);  // 到右端点距离
        }
    }
    
    // 计算点到下边界线段的最短距离
    double dist_to_bottom_segment(int x, int y) {
        if (0 <= x && x <= Cx) {
            return abs(y);  // 垂直距离
        } else if (x < 0) {
            return dist(0, 0, x, y);  // 到左端点距离
        } else {
            return dist(Cx, 0, x, y);  // 到右端点距离
        }
    }
    
    // 判断两个圆形是否相交（包括相切）
    bool circles_intersect(int i, int j) {
        double center_dist = dist(circles[i].x, circles[i].y, circles[j].x, circles[j].y);
        double radius_sum = circles[i].r + circles[j].r;
        return sign(center_dist - radius_sum) <= 0;
    }
    
    // 判断两个矩形是否相交
    bool rects_intersect(int i, int j) {
        // 检查矩形i的四个角点是否在矩形j内
        bool corner_in = point_in_segment(rects[i].x, rects[j].y, rects[j].Y, rects[i].y, rects[j].x, rects[j].X) ||
                        point_in_segment(rects[i].x, rects[j].y, rects[j].Y, rects[i].Y, rects[j].x, rects[j].X) ||
                        point_in_segment(rects[i].X, rects[j].y, rects[j].Y, rects[i].y, rects[j].x, rects[j].X) ||
                        point_in_segment(rects[i].X, rects[j].y, rects[j].Y, rects[i].Y, rects[j].x, rects[j].X);
        
        // 检查矩形j的四个角点是否在矩形i内
        corner_in = corner_in || 
                   point_in_segment(rects[j].x, rects[i].y, rects[i].Y, rects[j].y, rects[i].x, rects[i].X) ||
                   point_in_segment(rects[j].x, rects[i].y, rects[i].Y, rects[j].Y, rects[i].x, rects[i].X) ||
                   point_in_segment(rects[j].X, rects[i].y, rects[i].Y, rects[j].y, rects[i].x, rects[i].X) ||
                   point_in_segment(rects[j].X, rects[i].y, rects[i].Y, rects[j].Y, rects[i].x, rects[i].X);
        
        return corner_in;
    }
    
    // 判断圆形和矩形是否相交
    bool circle_rect_intersect(int circle_idx, int rect_idx) {
        Circle& c = circles[circle_idx];
        Rectangle& r = rects[rect_idx];
        
        // 找到矩形上距离圆心最近的点
        int closest_x = max(r.x, min(c.x, r.X));
        int closest_y = max(r.y, min(c.y, r.Y));
        
        // 计算圆心到最近点的距离
        double dist_to_closest = dist(c.x, c.y, closest_x, closest_y);
        
        return sign(dist_to_closest - c.r) <= 0;
    }
};

// 网络流类（Dinic算法）
class MaxFlow {
private:
    struct Edge {
        int to, next, cap, flow;
    };
    
    vector<Edge> edges;
    vector<int> head, level, current;
    int node_count, source, sink;
    
public:
    MaxFlow(int n, int s, int t) : node_count(n), source(s), sink(t) {
        head.resize(n + 1, -1);
    }
    
    // 添加边
    void add_edge(int u, int v, int cap) {
        edges.push_back({v, head[u], cap, 0});
        head[u] = edges.size() - 1;
        edges.push_back({u, head[v], 0, 0});
        head[v] = edges.size() - 1;
    }
    
    // BFS分层
    bool bfs() {
        level.assign(node_count + 1, -1);
        queue<int> q;
        q.push(source);
        level[source] = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int i = head[u]; i != -1; i = edges[i].next) {
                int v = edges[i].to;
                if (level[v] == -1 && edges[i].cap > edges[i].flow) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        
        return level[sink] != -1;
    }
    
    // DFS增广
    int dfs(int u, int flow) {
        if (u == sink || flow == 0) return flow;
        
        int total_flow = 0;
        for (int& i = current[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (level[v] == level[u] + 1 && edges[i].cap > edges[i].flow) {
                int pushed = dfs(v, min(flow, edges[i].cap - edges[i].flow));
                if (pushed > 0) {
                    edges[i].flow += pushed;
                    edges[i ^ 1].flow -= pushed;
                    total_flow += pushed;
                    flow -= pushed;
                    if (flow == 0) break;
                }
            }
        }
        return total_flow;
    }
    
    // 计算最大流
    int compute_max_flow() {
        int max_flow = 0;
        while (bfs()) {
            current = head;
            while (int flow = dfs(source, inf)) {
                max_flow += flow;
            }
        }
        return max_flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // 读入通道尺寸和元件数量
    cin >> Cx >> Cy >> n;
    
    GeometryUtils geo;
    
    // 读入元件信息
    _for(i, 1, n) {
        int type;
        cin >> type;
        
        if (type == 1) {
            // 圆形元件
            circle_cnt++;
            cin >> circles[circle_cnt].x >> circles[circle_cnt].y >> circles[circle_cnt].r;
            circles[circle_cnt].id = i;
        } else {
            // 矩形元件
            rect_cnt++;
            cin >> rects[rect_cnt].x >> rects[rect_cnt].y >> rects[rect_cnt].X >> rects[rect_cnt].Y;
            rects[rect_cnt].id = i;
        }
    }
    
    // 构建网络流图
    // 节点编号：1~n 为入点，n+1~2n 为出点
    int source = 0, sink = 2 * n + 1;
    MaxFlow flow_solver(2 * n + 2, source, sink);
    
    // 节点拆分：每个元件拆分为入点和出点，容量为1（代表可以移除）
    _for(i, 1, n) {
        flow_solver.add_edge(i, i + n, 1);
    }
    
    // 添加元件间的相交关系边
    // 圆形-圆形相交
    _for(i, 1, circle_cnt) {
        _for(j, i + 1, circle_cnt) {
            if (geo.circles_intersect(i, j)) {
                int id1 = circles[i].id;
                int id2 = circles[j].id;
                flow_solver.add_edge(id1 + n, id2, inf);
                flow_solver.add_edge(id2 + n, id1, inf);
            }
        }
    }
    
    // 矩形-矩形相交
    _for(i, 1, rect_cnt) {
        _for(j, i + 1, rect_cnt) {
            if (geo.rects_intersect(i, j)) {
                int id1 = rects[i].id;
                int id2 = rects[j].id;
                flow_solver.add_edge(id1 + n, id2, inf);
                flow_solver.add_edge(id2 + n, id1, inf);
            }
        }
    }
    
    // 圆形-矩形相交
    _for(i, 1, circle_cnt) {
        _for(j, 1, rect_cnt) {
            if (geo.circle_rect_intersect(i, j)) {
                int circle_id = circles[i].id;
                int rect_id = rects[j].id;
                flow_solver.add_edge(circle_id + n, rect_id, inf);
                flow_solver.add_edge(rect_id + n, circle_id, inf);
            }
        }
    }
    
    // 连接边界元件
    // 接触上边界的元件连接源点
    _for(i, 1, circle_cnt) {
        if (geo.circle_touches_top(i)) {
            flow_solver.add_edge(source, circles[i].id, inf);
        }
    }
    _for(i, 1, rect_cnt) {
        if (geo.rect_touches_top(i)) {
            flow_solver.add_edge(source, rects[i].id, inf);
        }
    }
    
    // 接触下边界的元件连接汇点
    _for(i, 1, circle_cnt) {
        if (geo.circle_touches_bottom(i)) {
            flow_solver.add_edge(circles[i].id + n, sink, inf);
        }
    }
    _for(i, 1, rect_cnt) {
        if (geo.rect_touches_bottom(i)) {
            flow_solver.add_edge(rects[i].id + n, sink, inf);
        }
    }
    
    // 计算最小割（最大流）
    int min_removal = flow_solver.compute_max_flow();
    cout << min_removal << "\n";
    
    return 0;
}

代码说明

关键数据结构

• Circle：存储圆形元件信息（圆心坐标、半径）
• Rectangle：存储矩形元件信息（左下角和右上角坐标）
• GeometryUtils：几何计算工具类
• MaxFlow：网络流求解类（Dinic算法）

算法核心

1. 图论建模

节点拆分技术：

• 每个元件对应两个节点：入点i和出点i+n
• 入点到出点的边容量为1，表示移除该元件的代价
• 这样可以将点割问题转化为边割问题

相交关系建模：

• 如果两个元件相交，在它们的出点和入点间添加双向无限容量边
• 这表示：如果保留这两个元件，它们会形成连通阻挡

2. 边界连接

• 源点S连接所有接触上边界的元件
• 所有接触下边界的元件连接汇点T
• 这样，任何从S到T的路径都代表一个完整的阻挡链

3. 几何相交检测

圆形-圆形相交：

• 判断圆心距离是否小于等于半径之和

矩形-矩形相交：

• 检查两个矩形的角点是否相互包含

圆形-矩形相交：

• 计算圆心到矩形的最短距离

数学原理

根据最大流最小割定理，从S到T的最大流等于最小割的容量。在这个模型中，最小割的容量就是需要移除的最少元件数量。

复杂度分析

• 几何检测：$O(n^2)$，其中 $n \leq 300$
• 网络流：Dinic算法 $O(n^2 \cdot m)$，其中 $m \leq n^2$
• 总复杂度：在题目数据范围内完全可行