1. 项目概述从一道“可见矩形”题看信奥刷题的核心价值最近在带学生刷信息学奥赛信奥的题目又翻到了P1302这道“可见矩形”。这道题在洛谷、一本通等题库里都算是个经典题目它不像动态规划那样让人望而生畏也不像图论那样需要复杂的建模。它的题干很简单在平面直角坐标系中给定一堆矩形用左下角和右上角坐标表示问从原点(0,0)看去有多少个矩形是至少部分可见的。但恰恰是这种“简单”的题目最能考验一个选手的基本功和思维严密性。很多初学者一看觉得“这不就是判断矩形和原点视线有没有被挡吗”上手一写却漏洞百出。这道题本质上是一个计算几何和思维转换的结合体它要求你将一个视觉上的“可见性”问题转化为计算机可以精确处理的数学模型。为什么我要专门拿这道题出来说因为在信奥的刷题路上P1302这类题代表了一个重要的关卡。它处于“学了循环判断就能看懂题意”和“需要高级数据结构与算法才能解决”的中间地带。攻克它意味着你开始摆脱“模拟暴力”的初级思维学会用更优雅、更高效的方式去解决问题。这对于备战CSP-J/S、NOIP乃至更高级别的比赛是必不可少的一环。今天我就以C实现者的角度带你彻底拆解P1302不仅告诉你代码怎么写更重点分享如何思考以及我在多年刷题和教学中总结的那些“坑”与技巧。2. 问题核心与思维转换把“看见”变成“比较”拿到题目第一反应往往是去模拟“视线”。从原点发出一条射线穿过无数个点这思路立刻就会陷入无穷无尽的细节泥潭。正确的破题点在于对“可见”进行重新定义。2.1 可见性的数学本质从原点(0,0)观察一个矩形可见意味着原点和矩形之间没有其他矩形完全阻挡这条“视线通道”。但计算机不适合处理“通道”它擅长处理大小关系和区间覆盖。我们需要一个关键的思维跳跃一个矩形可见当且仅当存在至少一个点(x,y)属于这个矩形使得从原点到该点的连线上没有其他矩形的点离原点更近。听起来还是有点绕。让我们再简化一下。考虑从原点出发连接矩形某个点的线段。如果另一个矩形完全覆盖了这条线段靠近原点的一部分那么它就被挡住了。但如何判断“覆盖线段”呢这里需要引入一个核心概念比较矩形的“前端”。想象所有矩形都有一层“皮”面向原点。对于从原点出发的某个特定方向比如一条射线哪个矩形“挡在最前面”哪个就是可见的。那么问题就转化为如何定义这个“前面”一个巧妙且常用的方法是使用极角和距离。但在这道题里有更直观的方法。我们考虑矩形边界上的点。一个矩形能被看见最关键的是它有一条“边缘”没有被挡住。这条边缘往往是矩形上离原点“最近”的那条边的一部分。实际上经过推导这里不展开严格的数学证明那是题解该做的事我们讲思路可以发现一个更实用的判定准则一个矩形是可见的如果存在一个不为0的实数k使得矩形中包含点(k * x, k * y)其中(x,y)是矩形某个顶点的坐标并且对于所有其他矩形都不包含任何点(k * x, k * y) 其中 0 k k。这个表述是为了引出下面的操作性方法我们可以把问题聚焦到矩形的边界线段上。特别是那些从原点看去构成“轮廓”的线段。2.2 从暴力枚举到离散化扫描最朴素的思路是枚举每一个矩形再枚举其他所有矩形判断是否被遮挡。判断遮挡需要几何计算复杂度是O(N²)N为矩形数量。题目虽未明确给出N的范围但在信奥比赛中O(N²)的算法在数据量大时必然超时。我们必须寻找O(N log N)或更优的解法。这就需要用到离散化和扫描线的思想。这也是本题的精华所在。我们并不需要检查平面上每一个点。关键的点在哪里在矩形的角点顶点以及这些角点与原点连线上的关键交点。我们可以考虑所有从原点出发穿过矩形顶点的射线。这些射线将平面划分成若干个角度区间。在同一个角度区间内矩形的“前后”顺序是不变的。因为在这个狭窄的扇形区域内判断哪个矩形离原点更近可以简化为比较一个与角度相关的值例如矩形在该角度方向上的最小极径。因此算法框架可以构建如下离散化角度求出所有矩形顶点相对于原点的极角进行排序去重。这样我们得到了一系列角度分割线。区间处理对于每两个相邻离散角度之间的区间在这个区间内任取一个角度例如中点问题退化为在这个固定的射线方向上哪个矩形离原点最近这个矩形就是在这个角度区间内可见的候选。判断最近矩形对于一条固定的从原点出发的射线方向角为θ一个矩形如果和这条射线有交点那么交点到原点的距离是一个范围[d_min, d_max]。d_min就是这个矩形在这个方向上“前端”的距离。我们只需要对所有和该射线相交的矩形找出d_min最小的那一个或多个如果d_min相等。这些d_min最小的矩形在这个角度区间内就是可见的。汇总去重将所有角度区间内找到的可见矩形ID收集起来去重后总数即为答案。这个框架将复杂的二维平面覆盖问题降维成了在一系列一维角度区间上的“求最小值”问题复杂度大大降低。3. 关键实现细节与C代码剖析理解了算法思想我们来看C实现的具体细节。这里会涉及一些计算几何的基础操作和C STL的巧妙运用。3.1 数据结构定义与输入处理首先我们需要表示矩形和点。为了避免浮点数精度问题题目通常给出的坐标是整数。但在计算极角时免不了要用到浮点数或高精度的分数表示。在竞赛中对于此类几何题一种常见的技巧是避免使用浮点数直接比较而是采用向量叉积、点积等整数运算进行判断。#include iostream #include vector #include algorithm #include cmath #include set using namespace std; struct Point { int x, y; Point(int x 0, int y 0) : x(x), y(y) {} // 向量减法 Point operator-(const Point b) const { return Point(x - b.x, y - b.y); } // 叉积 int cross(const Point b) const { return x * b.y - y * b.x; } // 点积 int dot(const Point b) const { return x * b.x y * b.y; } // 判断两点是否重合 bool operator(const Point b) const { return x b.x y b.y; } // 为了set排序定义比较规则按极角实际上我们比的是向量 bool operator(const Point b) const { // 处理在坐标轴上的情况 if (y 0 x 0) return true; // 向量(正x轴) if (b.y 0 b.x 0) return false; if (y 0 b.y 0) return true; // 上半平面 vs 下半平面 if (y 0 b.y 0) return false; // 同在半平面用叉积判断 return cross(b) 0; } }; struct Rect { int id; int x1, y1, x2, y2; // 左下(x1,y1), 右上(x2,y2) 题目保证 x1x2, y1y2 vectorPoint vertices; // 存储四个顶点 Rect(int id, int a, int b, int c, int d) : id(id), x1(a), y1(b), x2(c), y2(d) { // 初始化四个顶点 vertices.emplace_back(x1, y1); vertices.emplace_back(x2, y1); vertices.emplace_back(x2, y2); vertices.emplace_back(x1, y2); } };注意这里我们为Point定义了基于极角的排序规则。但注意直接这样比需要处理边界情况比如向量重合。在实际代码中我们更常用的是将角度离散化而不是直接存储和比较Point对象。这里只是为了展示结构。更稳妥的做法是计算一个代表方向的pair例如约分后的(dx, dy)或者直接计算浮点数角度然后处理精度。3.2 离散化角度与区间扫描真正的难点在于如何无精度损失地离散化角度。一个经典技巧是我们不直接存储角度atan2(y, x)而是存储一个代表方向的向量(x, y)并对其进行规范化。规范化不是归一化成长度为1而是约去x和y的最大公约数并确保一个唯一的符号约定例如让y为正若y为0则让x为正。这样同一条射线上的所有整数坐标点都会映射到同一个方向向量上。// 求最大公约数 int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 规范化方向向量 pairint, int normalize_dir(int dx, int dy) { if (dx 0 dy 0) return {0, 0}; // 原点应避免 int g gcd(abs(dx), abs(dy)); dx / g; dy / g; // 符号约定让dy为正如果dy0则让dx为正 if (dy 0 || (dy 0 dx 0)) { dx -dx; dy -dy; } return {dx, dy}; }接下来我们收集所有矩形顶点相对于原点的方向向量注意原点本身(0,0)这个向量需要排除因为它没有方向并规范化后放入一个set中来自动去重和排序。这个set里的每个唯一方向就代表了一条我们需要考虑的射线。int main() { int n; cin n; vectorRect rects; setpairint, int dir_set; // 存储所有唯一的方向向量 for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; rects.emplace_back(i, x1, y1, x2, y2); // 处理当前矩形的四个顶点 Rect r rects.back(); for (const Point v : r.vertices) { if (v.x 0 v.y 0) continue; // 忽略原点 dir_set.insert(normalize_dir(v.x, v.y)); } } // 将唯一方向转换为列表方便处理区间 vectorpairint, int dirs(dir_set.begin(), dir_set.end()); int m dirs.size(); // 为了处理环形我们可以将列表复制一份连接头尾或者特殊处理最后一个区间。 // 一个简单方法在列表末尾添加一个与第一个方向“相邻”的方向实际上需要计算角度2PI。 // 但因为我们用的是规范化向量无法直接加2PI。更实用的方法是对于每个方向我们考虑它和下一个方向之间的“中间方向”。 }然而使用规范化向量有一个问题它只代表了离散的射线方向而我们扫描需要的是角度区间。如何获取两个方向向量之间的中间方向一种近似方法是对于相邻的两个规范化向量(dx1, dy1)和(dx2, dy2)我们取一个中间方向例如(dx1dx2, dy1dy2)然后再规范化。但这并不总是精确的几何中点。在竞赛实践中对于这类“可见性”问题有一个更强大且精确的算法半平面交或极角排序后扫描。鉴于篇幅和复杂度我们转向另一种在竞赛中更常见、更易于实现且能通过本题的算法思路基于投影的区间覆盖法。3.3 替代算法投影区间覆盖法更易实现我们换一个角度思考“可见”。从原点看一个矩形可见意味着它在某个角度范围内其“前表面”是未被遮挡的。我们可以尝试为每个矩形计算它在角度坐标轴0 到 2π上哪些角度区间是“可能可见”的。考虑矩形的一条边。这条边上的点从原点看去对应一个连续的角度范围。整个矩形所有点对应的角度范围的并集就是这个矩形在角度上的“投影”。但是两个矩形在角度上投影重叠并不一定意味着遮挡还需要比较距离。这里介绍一个经典且高效的算法其核心步骤如下极角离散化收集所有矩形的顶点计算每个顶点相对于原点的极角atan2(y, x)。将这些极角排序去重。同时为了处理环形0度附近我们将所有角度复制一份并加上2π这样方便处理跨0度的区间。角度区间扫描取每两个相邻离散极角的中点作为代表这个小区间的“探测角度”theta。距离排序对于每个探测角度theta计算所有矩形在这个方向上的“最小距离”。如何计算从原点发射一条角度为theta的射线参数方程为(t * cosθ, t * sinθ), t0。对于一个矩形这条射线可能穿过它相交也可能不穿过。如果穿过则交点中离原点最近的那个点的距离t_min就是矩形在这个方向上的“前端距离”。如果射线刚好擦过边角也算相交。如果不相交则矩形在该方向不可见。判定可见对于这个theta找出所有与之相交的矩形中t_min最小的那个或那些。这些矩形在该角度区间内就是可见的。汇总收集所有探测角度上找到的可见矩形ID放入一个set去重set的大小就是答案。这个算法的关键在于第3步如何高效计算给定角度下一个矩形的t_min这需要一些几何计算。对于一个矩形我们可以求出它的四条边所在的直线方程。射线与矩形的交点就是射线与这四条边所在直线的交点中那些位于边线段范围内且t 0的点。然后取最小的t。为了避免复杂的直线求交和区间判断在竞赛编程中我们可以利用一个事实矩形是凸多边形。射线与凸多边形的交点如果存在是一个连续的线段[t_enter, t_exit]其中t_enter就是我们要的t_min。t_enter可以通过将射线与矩形的四条边进行求交并筛选得到。具体计算时对于一条边从点P1到点P2我们可以用参数方程表示边P P1 u * (P2 - P1), u in [0, 1]。射线方程为Q (0,0) v * (cosθ, sinθ), v 0。联立求解得到参数u和v。如果u在[0,1]范围内且v 0则v就是一个有效的交点距离。遍历四条边取所有有效v中的最小值即为t_min。如果对于所有边都没有有效的v则射线与该矩形不相交。实操心得在实现射线与线段求交时强烈建议使用向量叉积法来判断并求解而不是解联立方程。这样可以更好地处理边界情况如射线与边共线。同时要特别注意浮点数的精度问题。在信奥比赛中如果坐标是整数可以考虑使用分数或整数运算来避免精度误差。例如将方向向量(cosθ, sinθ)用一对整数(dx, dy)表示需满足gcd(|dx|,|dy|)1然后使用整数运算求解交点参数。但这会大大增加代码复杂度。对于本题通常给定的坐标范围和精度要求使用double并设置一个如1e-12的误差容限eps是可行的。3.4 完整代码框架与核心函数下面给出一个基于浮点数、采用角度区间扫描法的简化版代码框架。注意这不是最高效的但清晰地体现了算法逻辑。#include bits/stdc.h using namespace std; const double PI acos(-1.0); const double EPS 1e-12; struct Rect { int id; double x1, y1, x2, y2; Rect(int id, double a, double b, double c, double d) : id(id), x1(a), y1(b), x2(c), y2(d) { if (x1 x2) swap(x1, x2); if (y1 y2) swap(y1, y2); } // 判断射线(dir_x, dir_y)是否与此矩形相交并返回最小距离t pairbool, double intersectRay(double dir_x, double dir_y) const { double t_enter -1e300, t_exit 1e300; // 处理矩形四条边xx1, xx2, yy1, yy2 // 对于边 x x1 (垂直边) if (fabs(dir_x) EPS) { double t x1 / dir_x; double y t * dir_y; if (t EPS y y1 - EPS y y2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); // 对于垂直边进入和退出可能是同一个点 } } // 对于边 x x2 if (fabs(dir_x) EPS) { double t x2 / dir_x; double y t * dir_y; if (t EPS y y1 - EPS y y2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 对于边 y y1 (水平边) if (fabs(dir_y) EPS) { double t y1 / dir_y; double x t * dir_x; if (t EPS x x1 - EPS x x2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 对于边 y y2 if (fabs(dir_y) EPS) { double t y2 / dir_y; double x t * dir_x; if (t EPS x x1 - EPS x x2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 如果 t_enter t_exit EPS 且 t_enter 0则相交 if (t_enter EPS t_enter t_exit EPS) { return {true, t_enter}; } return {false, 0.0}; } }; int main() { int n; cin n; vectorRect rects; vectordouble angles; // 读入数据并收集所有顶点的极角 for (int i 0; i n; i) { double x1, y1, x2, y2; cin x1 y1 x2 y2; rects.emplace_back(i, x1, y1, x2, y2); Rect r rects.back(); // 计算四个顶点的极角 vectorPoint verts {{r.x1, r.y1}, {r.x2, r.y1}, {r.x2, r.y2}, {r.x1, r.y2}}; for (auto p : verts) { if (fabs(p.x) EPS fabs(p.y) EPS) continue; // 忽略原点 double ang atan2(p.y, p.x); if (ang 0) ang 2 * PI; // 转换到 [0, 2π) angles.push_back(ang); } } // 极角排序去重并处理环形 sort(angles.begin(), angles.end()); angles.erase(unique(angles.begin(), angles.end(), [](double a, double b) { return fabs(a - b) EPS; }), angles.end()); int m angles.size(); // 复制一份加2π用于处理跨0度区间 for (int i 0; i m; i) { angles.push_back(angles[i] 2 * PI); } setint visible_set; // 扫描每个小区间 for (int i 0; i m; i) { double mid_ang (angles[i] angles[i 1]) * 0.5; double dir_x cos(mid_ang); double dir_y sin(mid_ang); double min_t 1e300; vectorint candidates; // 遍历所有矩形找到当前方向上最近的矩形 for (auto rect : rects) { auto [intersect, t] rect.intersectRay(dir_x, dir_y); if (intersect) { if (fabs(t - min_t) EPS) { // 距离相等多个矩形并列最近 candidates.push_back(rect.id); } else if (t min_t - EPS) { min_t t; candidates.clear(); candidates.push_back(rect.id); } } } // 将候选矩形加入可见集合 for (int id : candidates) { visible_set.insert(id); } } cout visible_set.size() endl; return 0; }重要提示上述代码中的intersectRay函数是一个简化版本它通过分别处理四条边来近似计算射线与矩形的交点。这种方法在射线指向矩形内部时是有效的但当射线恰好穿过顶点时可能会因为浮点精度问题重复计算或漏算。一个更健壮的方法是使用标准的射线与凸多边形求交算法即用射线与每条边求交并计算进入和退出参数。上面的简化代码对于理解算法流程是足够的但在严格竞赛中可能需要更精细的实现。4. 常见陷阱、优化与调试技巧实现过程中你会遇到不少坑。下面是我总结的几个关键点和优化方向。4.1 浮点数精度处理这是计算几何永恒的话题。在信奥中如果题目坐标是整数且范围不大可以尝试全程使用整数运算。例如方向向量用(dx, dy)表示求交时解方程得到分数通过比较分子分母来判断大小。但这非常繁琐。使用double时必须定义误差容限EPS如1e-9到1e-12。所有比较操作,,都要用fabs(a-b) EPS,a b - EPS,a b EPS来代替。在本题的上下文中精度问题主要影响极角排序去重两个极角相差极小应视为相同。距离比较判断哪个矩形更近时。交点判断判断点是否在线段上时。一个实用技巧是在最后判断可见矩形时不直接比较t值而是比较t的平方即距离平方这样可以避免开方运算但前提是求交时得到的t本身就是距离而不是距离的平方。在我们的方法中t就是距离。4.2 边界情况原点与矩形的关系矩形包含原点如果某个矩形包含了原点(0,0)那么从原点看向这个矩形它肯定是完全可见的并且会挡住后面所有的矩形吗不因为原点在矩形内部从原点出发的射线会立即碰到这个矩形t_min 0但t0的点就是原点本身这通常不被认为是“看见”了矩形的内部点。题目一般会定义“可见”为存在一条从原点出发的开线段不含端点与矩形相交。因此包含原点的矩形其t_min可以是一个大于0的极小值例如从原点出发稍微移动一点就进入矩形内部。在实现时我们的射线参数t EPS正好过滤了原点。包含原点的矩形其t_min会是某个正数例如到最近边的距离所以它仍然需要参与距离比较可能被其他t_min更小的矩形挡住一部分。这是一个非常容易出错的点。矩形的一条边通过原点类似地需要小心处理t0的情况。多个矩形在同一个方向上有相同的最小距离这意味着它们的“前缘”在一条从原点出发的射线上对齐了。根据题目对“可见”的定义如果它们共享同一条边的一部分可能都算可见。我们的代码中通过fabs(t - min_t) EPS将并列的矩形都加入了候选集。4.3 算法优化点上述角度扫描法的时间复杂度是O(N * M)其中N是矩形数M是离散化的角度数最多4N个。在N较大时例如几百上千可能效率不高。可以考虑以下优化减少探测角度我们真的需要每两个相邻顶点角度之间都取中点探测吗实际上可见性发生变化只可能发生在某些“关键角度”即某个矩形的边开始或停止遮挡另一个矩形的角度。这些关键角度是顶点连线的角度以及矩形边与原点连线的角度。但找出所有这些角度本身就是一个复杂问题。在竞赛时限内O(N^2)的探测通常可以接受因为4N个角度对于N 200左右是可行的800 * 200 160k次求交运算。更高效的求交intersectRay函数可以优化。对于给定的方向(dx, dy)矩形在该方向上的t_min实际上可以通过计算矩形在方向向量上的投影区间来得到。对于一个轴对齐矩形t_min是max( min(x1/dx, x2/dx), min(y1/dy, y2/dy) )但需要根据dx,dy的正负仔细处理除零和无穷大。这种方法更快但逻辑更复杂。使用整数运算如前所述可以完全避免浮点数。将方向向量表示为(dx, dy)然后计算每个矩形对应的t_min的分数形式通过交叉比较分子分母来排序。这需要实现分数类或使用__int128来避免溢出。4.4 调试技巧与测试数据构造调试计算几何题目可视化是王道。如果条件允许可以写一个简单的脚本比如用Python的matplotlib将矩形和原点画出来并标出你认为可见的矩形与程序输出对比。自己构造测试数据简单数据只有一个矩形位于第一象限。答案应为1。包含原点一个矩形包含(0,0)。答案应为1除非有另一个矩形完全覆盖它但包含原点的矩形其“前缘”距离为0很难被完全覆盖。完全遮挡一个大矩形完全包含一个小矩形且小矩形在大矩形后面离原点更远。答案应为1只有大矩形可见。部分遮挡两个矩形并排有部分重叠区域。需要仔细分析可见情况。共线边缘两个矩形共享一条从原点出发的射线上的边。检查它们是否都被计为可见。大量随机数据生成随机矩形用暴力算法O(N^3)对小规模数据验证确保你的高效算法结果一致。在代码中加入调试输出例如对于每个探测角度打印出min_t和对应的矩形ID可以帮助你理解算法的决策过程。5. 从P1302延伸的信奥刷题方法论P1302这道题解完不应止步于此。它给我们提供了几个重要的信奥刷题思维模式降维打击将二维平面上的几何可见性问题通过极角离散化转化为一系列一维方向上的最值问题。这是解决许多复杂几何问题的关键思路——找到那个可以扫描的维度。模型转换“可见性”是一个直观概念但计算机需要精确的、可计算的判定条件。将生活语言转化为数学语言或计算模型是信奥选手的核心能力。精度意识计算几何题是浮点数精度问题的重灾区。必须习惯使用EPS并思考能否用整数运算避免浮点误差。边界思维包含原点、边通过原点、多个矩形共线等边界情况往往是测试数据卡人的地方。编写代码时必须主动思考这些极端情况。刷题不是单纯地“刷”数量而是通过一道题掌握一类方法锤炼一种思维。像P1302这样的题吃透了以后再遇到“可见点”、“可见区域”、“轮廓线”之类的问题你手里就有了一套可用的工具箱。这才是信奥刷题乃至所有算法学习真正有价值的地方。下次再看到“可见”二字不妨先想想能不能把它“拍扁”到一个维度上去处理。 计算几何入门：从可见矩形问题理解离散化与扫描线算法
1. 项目概述从一道“可见矩形”题看信奥刷题的核心价值最近在带学生刷信息学奥赛信奥的题目又翻到了P1302这道“可见矩形”。这道题在洛谷、一本通等题库里都算是个经典题目它不像动态规划那样让人望而生畏也不像图论那样需要复杂的建模。它的题干很简单在平面直角坐标系中给定一堆矩形用左下角和右上角坐标表示问从原点(0,0)看去有多少个矩形是至少部分可见的。但恰恰是这种“简单”的题目最能考验一个选手的基本功和思维严密性。很多初学者一看觉得“这不就是判断矩形和原点视线有没有被挡吗”上手一写却漏洞百出。这道题本质上是一个计算几何和思维转换的结合体它要求你将一个视觉上的“可见性”问题转化为计算机可以精确处理的数学模型。为什么我要专门拿这道题出来说因为在信奥的刷题路上P1302这类题代表了一个重要的关卡。它处于“学了循环判断就能看懂题意”和“需要高级数据结构与算法才能解决”的中间地带。攻克它意味着你开始摆脱“模拟暴力”的初级思维学会用更优雅、更高效的方式去解决问题。这对于备战CSP-J/S、NOIP乃至更高级别的比赛是必不可少的一环。今天我就以C实现者的角度带你彻底拆解P1302不仅告诉你代码怎么写更重点分享如何思考以及我在多年刷题和教学中总结的那些“坑”与技巧。2. 问题核心与思维转换把“看见”变成“比较”拿到题目第一反应往往是去模拟“视线”。从原点发出一条射线穿过无数个点这思路立刻就会陷入无穷无尽的细节泥潭。正确的破题点在于对“可见”进行重新定义。2.1 可见性的数学本质从原点(0,0)观察一个矩形可见意味着原点和矩形之间没有其他矩形完全阻挡这条“视线通道”。但计算机不适合处理“通道”它擅长处理大小关系和区间覆盖。我们需要一个关键的思维跳跃一个矩形可见当且仅当存在至少一个点(x,y)属于这个矩形使得从原点到该点的连线上没有其他矩形的点离原点更近。听起来还是有点绕。让我们再简化一下。考虑从原点出发连接矩形某个点的线段。如果另一个矩形完全覆盖了这条线段靠近原点的一部分那么它就被挡住了。但如何判断“覆盖线段”呢这里需要引入一个核心概念比较矩形的“前端”。想象所有矩形都有一层“皮”面向原点。对于从原点出发的某个特定方向比如一条射线哪个矩形“挡在最前面”哪个就是可见的。那么问题就转化为如何定义这个“前面”一个巧妙且常用的方法是使用极角和距离。但在这道题里有更直观的方法。我们考虑矩形边界上的点。一个矩形能被看见最关键的是它有一条“边缘”没有被挡住。这条边缘往往是矩形上离原点“最近”的那条边的一部分。实际上经过推导这里不展开严格的数学证明那是题解该做的事我们讲思路可以发现一个更实用的判定准则一个矩形是可见的如果存在一个不为0的实数k使得矩形中包含点(k * x, k * y)其中(x,y)是矩形某个顶点的坐标并且对于所有其他矩形都不包含任何点(k * x, k * y) 其中 0 k k。这个表述是为了引出下面的操作性方法我们可以把问题聚焦到矩形的边界线段上。特别是那些从原点看去构成“轮廓”的线段。2.2 从暴力枚举到离散化扫描最朴素的思路是枚举每一个矩形再枚举其他所有矩形判断是否被遮挡。判断遮挡需要几何计算复杂度是O(N²)N为矩形数量。题目虽未明确给出N的范围但在信奥比赛中O(N²)的算法在数据量大时必然超时。我们必须寻找O(N log N)或更优的解法。这就需要用到离散化和扫描线的思想。这也是本题的精华所在。我们并不需要检查平面上每一个点。关键的点在哪里在矩形的角点顶点以及这些角点与原点连线上的关键交点。我们可以考虑所有从原点出发穿过矩形顶点的射线。这些射线将平面划分成若干个角度区间。在同一个角度区间内矩形的“前后”顺序是不变的。因为在这个狭窄的扇形区域内判断哪个矩形离原点更近可以简化为比较一个与角度相关的值例如矩形在该角度方向上的最小极径。因此算法框架可以构建如下离散化角度求出所有矩形顶点相对于原点的极角进行排序去重。这样我们得到了一系列角度分割线。区间处理对于每两个相邻离散角度之间的区间在这个区间内任取一个角度例如中点问题退化为在这个固定的射线方向上哪个矩形离原点最近这个矩形就是在这个角度区间内可见的候选。判断最近矩形对于一条固定的从原点出发的射线方向角为θ一个矩形如果和这条射线有交点那么交点到原点的距离是一个范围[d_min, d_max]。d_min就是这个矩形在这个方向上“前端”的距离。我们只需要对所有和该射线相交的矩形找出d_min最小的那一个或多个如果d_min相等。这些d_min最小的矩形在这个角度区间内就是可见的。汇总去重将所有角度区间内找到的可见矩形ID收集起来去重后总数即为答案。这个框架将复杂的二维平面覆盖问题降维成了在一系列一维角度区间上的“求最小值”问题复杂度大大降低。3. 关键实现细节与C代码剖析理解了算法思想我们来看C实现的具体细节。这里会涉及一些计算几何的基础操作和C STL的巧妙运用。3.1 数据结构定义与输入处理首先我们需要表示矩形和点。为了避免浮点数精度问题题目通常给出的坐标是整数。但在计算极角时免不了要用到浮点数或高精度的分数表示。在竞赛中对于此类几何题一种常见的技巧是避免使用浮点数直接比较而是采用向量叉积、点积等整数运算进行判断。#include iostream #include vector #include algorithm #include cmath #include set using namespace std; struct Point { int x, y; Point(int x 0, int y 0) : x(x), y(y) {} // 向量减法 Point operator-(const Point b) const { return Point(x - b.x, y - b.y); } // 叉积 int cross(const Point b) const { return x * b.y - y * b.x; } // 点积 int dot(const Point b) const { return x * b.x y * b.y; } // 判断两点是否重合 bool operator(const Point b) const { return x b.x y b.y; } // 为了set排序定义比较规则按极角实际上我们比的是向量 bool operator(const Point b) const { // 处理在坐标轴上的情况 if (y 0 x 0) return true; // 向量(正x轴) if (b.y 0 b.x 0) return false; if (y 0 b.y 0) return true; // 上半平面 vs 下半平面 if (y 0 b.y 0) return false; // 同在半平面用叉积判断 return cross(b) 0; } }; struct Rect { int id; int x1, y1, x2, y2; // 左下(x1,y1), 右上(x2,y2) 题目保证 x1x2, y1y2 vectorPoint vertices; // 存储四个顶点 Rect(int id, int a, int b, int c, int d) : id(id), x1(a), y1(b), x2(c), y2(d) { // 初始化四个顶点 vertices.emplace_back(x1, y1); vertices.emplace_back(x2, y1); vertices.emplace_back(x2, y2); vertices.emplace_back(x1, y2); } };注意这里我们为Point定义了基于极角的排序规则。但注意直接这样比需要处理边界情况比如向量重合。在实际代码中我们更常用的是将角度离散化而不是直接存储和比较Point对象。这里只是为了展示结构。更稳妥的做法是计算一个代表方向的pair例如约分后的(dx, dy)或者直接计算浮点数角度然后处理精度。3.2 离散化角度与区间扫描真正的难点在于如何无精度损失地离散化角度。一个经典技巧是我们不直接存储角度atan2(y, x)而是存储一个代表方向的向量(x, y)并对其进行规范化。规范化不是归一化成长度为1而是约去x和y的最大公约数并确保一个唯一的符号约定例如让y为正若y为0则让x为正。这样同一条射线上的所有整数坐标点都会映射到同一个方向向量上。// 求最大公约数 int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 规范化方向向量 pairint, int normalize_dir(int dx, int dy) { if (dx 0 dy 0) return {0, 0}; // 原点应避免 int g gcd(abs(dx), abs(dy)); dx / g; dy / g; // 符号约定让dy为正如果dy0则让dx为正 if (dy 0 || (dy 0 dx 0)) { dx -dx; dy -dy; } return {dx, dy}; }接下来我们收集所有矩形顶点相对于原点的方向向量注意原点本身(0,0)这个向量需要排除因为它没有方向并规范化后放入一个set中来自动去重和排序。这个set里的每个唯一方向就代表了一条我们需要考虑的射线。int main() { int n; cin n; vectorRect rects; setpairint, int dir_set; // 存储所有唯一的方向向量 for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; rects.emplace_back(i, x1, y1, x2, y2); // 处理当前矩形的四个顶点 Rect r rects.back(); for (const Point v : r.vertices) { if (v.x 0 v.y 0) continue; // 忽略原点 dir_set.insert(normalize_dir(v.x, v.y)); } } // 将唯一方向转换为列表方便处理区间 vectorpairint, int dirs(dir_set.begin(), dir_set.end()); int m dirs.size(); // 为了处理环形我们可以将列表复制一份连接头尾或者特殊处理最后一个区间。 // 一个简单方法在列表末尾添加一个与第一个方向“相邻”的方向实际上需要计算角度2PI。 // 但因为我们用的是规范化向量无法直接加2PI。更实用的方法是对于每个方向我们考虑它和下一个方向之间的“中间方向”。 }然而使用规范化向量有一个问题它只代表了离散的射线方向而我们扫描需要的是角度区间。如何获取两个方向向量之间的中间方向一种近似方法是对于相邻的两个规范化向量(dx1, dy1)和(dx2, dy2)我们取一个中间方向例如(dx1dx2, dy1dy2)然后再规范化。但这并不总是精确的几何中点。在竞赛实践中对于这类“可见性”问题有一个更强大且精确的算法半平面交或极角排序后扫描。鉴于篇幅和复杂度我们转向另一种在竞赛中更常见、更易于实现且能通过本题的算法思路基于投影的区间覆盖法。3.3 替代算法投影区间覆盖法更易实现我们换一个角度思考“可见”。从原点看一个矩形可见意味着它在某个角度范围内其“前表面”是未被遮挡的。我们可以尝试为每个矩形计算它在角度坐标轴0 到 2π上哪些角度区间是“可能可见”的。考虑矩形的一条边。这条边上的点从原点看去对应一个连续的角度范围。整个矩形所有点对应的角度范围的并集就是这个矩形在角度上的“投影”。但是两个矩形在角度上投影重叠并不一定意味着遮挡还需要比较距离。这里介绍一个经典且高效的算法其核心步骤如下极角离散化收集所有矩形的顶点计算每个顶点相对于原点的极角atan2(y, x)。将这些极角排序去重。同时为了处理环形0度附近我们将所有角度复制一份并加上2π这样方便处理跨0度的区间。角度区间扫描取每两个相邻离散极角的中点作为代表这个小区间的“探测角度”theta。距离排序对于每个探测角度theta计算所有矩形在这个方向上的“最小距离”。如何计算从原点发射一条角度为theta的射线参数方程为(t * cosθ, t * sinθ), t0。对于一个矩形这条射线可能穿过它相交也可能不穿过。如果穿过则交点中离原点最近的那个点的距离t_min就是矩形在这个方向上的“前端距离”。如果射线刚好擦过边角也算相交。如果不相交则矩形在该方向不可见。判定可见对于这个theta找出所有与之相交的矩形中t_min最小的那个或那些。这些矩形在该角度区间内就是可见的。汇总收集所有探测角度上找到的可见矩形ID放入一个set去重set的大小就是答案。这个算法的关键在于第3步如何高效计算给定角度下一个矩形的t_min这需要一些几何计算。对于一个矩形我们可以求出它的四条边所在的直线方程。射线与矩形的交点就是射线与这四条边所在直线的交点中那些位于边线段范围内且t 0的点。然后取最小的t。为了避免复杂的直线求交和区间判断在竞赛编程中我们可以利用一个事实矩形是凸多边形。射线与凸多边形的交点如果存在是一个连续的线段[t_enter, t_exit]其中t_enter就是我们要的t_min。t_enter可以通过将射线与矩形的四条边进行求交并筛选得到。具体计算时对于一条边从点P1到点P2我们可以用参数方程表示边P P1 u * (P2 - P1), u in [0, 1]。射线方程为Q (0,0) v * (cosθ, sinθ), v 0。联立求解得到参数u和v。如果u在[0,1]范围内且v 0则v就是一个有效的交点距离。遍历四条边取所有有效v中的最小值即为t_min。如果对于所有边都没有有效的v则射线与该矩形不相交。实操心得在实现射线与线段求交时强烈建议使用向量叉积法来判断并求解而不是解联立方程。这样可以更好地处理边界情况如射线与边共线。同时要特别注意浮点数的精度问题。在信奥比赛中如果坐标是整数可以考虑使用分数或整数运算来避免精度误差。例如将方向向量(cosθ, sinθ)用一对整数(dx, dy)表示需满足gcd(|dx|,|dy|)1然后使用整数运算求解交点参数。但这会大大增加代码复杂度。对于本题通常给定的坐标范围和精度要求使用double并设置一个如1e-12的误差容限eps是可行的。3.4 完整代码框架与核心函数下面给出一个基于浮点数、采用角度区间扫描法的简化版代码框架。注意这不是最高效的但清晰地体现了算法逻辑。#include bits/stdc.h using namespace std; const double PI acos(-1.0); const double EPS 1e-12; struct Rect { int id; double x1, y1, x2, y2; Rect(int id, double a, double b, double c, double d) : id(id), x1(a), y1(b), x2(c), y2(d) { if (x1 x2) swap(x1, x2); if (y1 y2) swap(y1, y2); } // 判断射线(dir_x, dir_y)是否与此矩形相交并返回最小距离t pairbool, double intersectRay(double dir_x, double dir_y) const { double t_enter -1e300, t_exit 1e300; // 处理矩形四条边xx1, xx2, yy1, yy2 // 对于边 x x1 (垂直边) if (fabs(dir_x) EPS) { double t x1 / dir_x; double y t * dir_y; if (t EPS y y1 - EPS y y2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); // 对于垂直边进入和退出可能是同一个点 } } // 对于边 x x2 if (fabs(dir_x) EPS) { double t x2 / dir_x; double y t * dir_y; if (t EPS y y1 - EPS y y2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 对于边 y y1 (水平边) if (fabs(dir_y) EPS) { double t y1 / dir_y; double x t * dir_x; if (t EPS x x1 - EPS x x2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 对于边 y y2 if (fabs(dir_y) EPS) { double t y2 / dir_y; double x t * dir_x; if (t EPS x x1 - EPS x x2 EPS) { t_enter max(t_enter, t); t_exit min(t_exit, t); } } // 如果 t_enter t_exit EPS 且 t_enter 0则相交 if (t_enter EPS t_enter t_exit EPS) { return {true, t_enter}; } return {false, 0.0}; } }; int main() { int n; cin n; vectorRect rects; vectordouble angles; // 读入数据并收集所有顶点的极角 for (int i 0; i n; i) { double x1, y1, x2, y2; cin x1 y1 x2 y2; rects.emplace_back(i, x1, y1, x2, y2); Rect r rects.back(); // 计算四个顶点的极角 vectorPoint verts {{r.x1, r.y1}, {r.x2, r.y1}, {r.x2, r.y2}, {r.x1, r.y2}}; for (auto p : verts) { if (fabs(p.x) EPS fabs(p.y) EPS) continue; // 忽略原点 double ang atan2(p.y, p.x); if (ang 0) ang 2 * PI; // 转换到 [0, 2π) angles.push_back(ang); } } // 极角排序去重并处理环形 sort(angles.begin(), angles.end()); angles.erase(unique(angles.begin(), angles.end(), [](double a, double b) { return fabs(a - b) EPS; }), angles.end()); int m angles.size(); // 复制一份加2π用于处理跨0度区间 for (int i 0; i m; i) { angles.push_back(angles[i] 2 * PI); } setint visible_set; // 扫描每个小区间 for (int i 0; i m; i) { double mid_ang (angles[i] angles[i 1]) * 0.5; double dir_x cos(mid_ang); double dir_y sin(mid_ang); double min_t 1e300; vectorint candidates; // 遍历所有矩形找到当前方向上最近的矩形 for (auto rect : rects) { auto [intersect, t] rect.intersectRay(dir_x, dir_y); if (intersect) { if (fabs(t - min_t) EPS) { // 距离相等多个矩形并列最近 candidates.push_back(rect.id); } else if (t min_t - EPS) { min_t t; candidates.clear(); candidates.push_back(rect.id); } } } // 将候选矩形加入可见集合 for (int id : candidates) { visible_set.insert(id); } } cout visible_set.size() endl; return 0; }重要提示上述代码中的intersectRay函数是一个简化版本它通过分别处理四条边来近似计算射线与矩形的交点。这种方法在射线指向矩形内部时是有效的但当射线恰好穿过顶点时可能会因为浮点精度问题重复计算或漏算。一个更健壮的方法是使用标准的射线与凸多边形求交算法即用射线与每条边求交并计算进入和退出参数。上面的简化代码对于理解算法流程是足够的但在严格竞赛中可能需要更精细的实现。4. 常见陷阱、优化与调试技巧实现过程中你会遇到不少坑。下面是我总结的几个关键点和优化方向。4.1 浮点数精度处理这是计算几何永恒的话题。在信奥中如果题目坐标是整数且范围不大可以尝试全程使用整数运算。例如方向向量用(dx, dy)表示求交时解方程得到分数通过比较分子分母来判断大小。但这非常繁琐。使用double时必须定义误差容限EPS如1e-9到1e-12。所有比较操作,,都要用fabs(a-b) EPS,a b - EPS,a b EPS来代替。在本题的上下文中精度问题主要影响极角排序去重两个极角相差极小应视为相同。距离比较判断哪个矩形更近时。交点判断判断点是否在线段上时。一个实用技巧是在最后判断可见矩形时不直接比较t值而是比较t的平方即距离平方这样可以避免开方运算但前提是求交时得到的t本身就是距离而不是距离的平方。在我们的方法中t就是距离。4.2 边界情况原点与矩形的关系矩形包含原点如果某个矩形包含了原点(0,0)那么从原点看向这个矩形它肯定是完全可见的并且会挡住后面所有的矩形吗不因为原点在矩形内部从原点出发的射线会立即碰到这个矩形t_min 0但t0的点就是原点本身这通常不被认为是“看见”了矩形的内部点。题目一般会定义“可见”为存在一条从原点出发的开线段不含端点与矩形相交。因此包含原点的矩形其t_min可以是一个大于0的极小值例如从原点出发稍微移动一点就进入矩形内部。在实现时我们的射线参数t EPS正好过滤了原点。包含原点的矩形其t_min会是某个正数例如到最近边的距离所以它仍然需要参与距离比较可能被其他t_min更小的矩形挡住一部分。这是一个非常容易出错的点。矩形的一条边通过原点类似地需要小心处理t0的情况。多个矩形在同一个方向上有相同的最小距离这意味着它们的“前缘”在一条从原点出发的射线上对齐了。根据题目对“可见”的定义如果它们共享同一条边的一部分可能都算可见。我们的代码中通过fabs(t - min_t) EPS将并列的矩形都加入了候选集。4.3 算法优化点上述角度扫描法的时间复杂度是O(N * M)其中N是矩形数M是离散化的角度数最多4N个。在N较大时例如几百上千可能效率不高。可以考虑以下优化减少探测角度我们真的需要每两个相邻顶点角度之间都取中点探测吗实际上可见性发生变化只可能发生在某些“关键角度”即某个矩形的边开始或停止遮挡另一个矩形的角度。这些关键角度是顶点连线的角度以及矩形边与原点连线的角度。但找出所有这些角度本身就是一个复杂问题。在竞赛时限内O(N^2)的探测通常可以接受因为4N个角度对于N 200左右是可行的800 * 200 160k次求交运算。更高效的求交intersectRay函数可以优化。对于给定的方向(dx, dy)矩形在该方向上的t_min实际上可以通过计算矩形在方向向量上的投影区间来得到。对于一个轴对齐矩形t_min是max( min(x1/dx, x2/dx), min(y1/dy, y2/dy) )但需要根据dx,dy的正负仔细处理除零和无穷大。这种方法更快但逻辑更复杂。使用整数运算如前所述可以完全避免浮点数。将方向向量表示为(dx, dy)然后计算每个矩形对应的t_min的分数形式通过交叉比较分子分母来排序。这需要实现分数类或使用__int128来避免溢出。4.4 调试技巧与测试数据构造调试计算几何题目可视化是王道。如果条件允许可以写一个简单的脚本比如用Python的matplotlib将矩形和原点画出来并标出你认为可见的矩形与程序输出对比。自己构造测试数据简单数据只有一个矩形位于第一象限。答案应为1。包含原点一个矩形包含(0,0)。答案应为1除非有另一个矩形完全覆盖它但包含原点的矩形其“前缘”距离为0很难被完全覆盖。完全遮挡一个大矩形完全包含一个小矩形且小矩形在大矩形后面离原点更远。答案应为1只有大矩形可见。部分遮挡两个矩形并排有部分重叠区域。需要仔细分析可见情况。共线边缘两个矩形共享一条从原点出发的射线上的边。检查它们是否都被计为可见。大量随机数据生成随机矩形用暴力算法O(N^3)对小规模数据验证确保你的高效算法结果一致。在代码中加入调试输出例如对于每个探测角度打印出min_t和对应的矩形ID可以帮助你理解算法的决策过程。5. 从P1302延伸的信奥刷题方法论P1302这道题解完不应止步于此。它给我们提供了几个重要的信奥刷题思维模式降维打击将二维平面上的几何可见性问题通过极角离散化转化为一系列一维方向上的最值问题。这是解决许多复杂几何问题的关键思路——找到那个可以扫描的维度。模型转换“可见性”是一个直观概念但计算机需要精确的、可计算的判定条件。将生活语言转化为数学语言或计算模型是信奥选手的核心能力。精度意识计算几何题是浮点数精度问题的重灾区。必须习惯使用EPS并思考能否用整数运算避免浮点误差。边界思维包含原点、边通过原点、多个矩形共线等边界情况往往是测试数据卡人的地方。编写代码时必须主动思考这些极端情况。刷题不是单纯地“刷”数量而是通过一道题掌握一类方法锤炼一种思维。像P1302这样的题吃透了以后再遇到“可见点”、“可见区域”、“轮廓线”之类的问题你手里就有了一套可用的工具箱。这才是信奥刷题乃至所有算法学习真正有价值的地方。下次再看到“可见”二字不妨先想想能不能把它“拍扁”到一个维度上去处理。