UVa 746 Polygon Visibility-北京尧图网络

题目描述给定两个互不相交的凸多边形非退化多边形顶点按顺时针顺序给出。需要求平面上所有点PPPPPP不在第一个多边形内部的集合使得存在QQQ属于第二个多边形且线段PQ‾\overline{PQ}PQ的内部与第一个多边形相交。该集合的边界由两条无限直线以及第一个多边形上的一段有限线段组成。要求输出这两条无限直线的斜率若为垂直直线则输出VERTICAL以及第一个多边形上构成有限线段的所有顶点且顶点按顺时针顺序给出。输入格式每个测试用例包含以下内容第一行两个正整数NNN和MMM3≤N,M≤100003 \le N, M \le 100003≤N,M≤10000分别表示第一个和第二个多边形的顶点数。接下来NNN行每行两个整数表示第一个多边形的顶点坐标按顺时针顺序给出。接下来MMM行每行两个整数表示第二个多边形的顶点坐标按顺时针顺序给出。坐标均为111到100001000010000之间的整数。输入以一行0 0结束该行不处理。输出格式对于每个测试用例输出以下内容第一行Instance X:XXX为用例编号从111开始。第二行第一条无限直线的斜率保留三位小数若为垂直直线输出VERTICAL。接下来若干行第一个多边形上从第二个切点顺时针到第一个切点的所有顶点包含两端每行输出坐标x y。最后一行第二条无限直线的斜率格式同上。两条无限直线均为内公切线顺序无严格要求但顶点序列需与样例一致。样例输入3 3 10 20 20 20 10 10 10 7 5 5 7 5 5 7 4 3 20 19 25 15 20 10 15 15 10 20 10 10 5 15 0 0输出Instance 1: VERTICAL 10 20 20 20 10 10 0.000 Instance 2: 1.000 15 15 20 19 25 15 20 10 -1.000题目分析本题要求找出所有从外部观察第二个多边形时视线被第一个多边形遮挡的点集。从几何上看该点集被两条内公切线和第一个多边形的一段边界所围成。内公切线的定义为一条直线同时与两个凸多边形相切且两个多边形分别位于直线的两侧。两条内公切线将两个凸多边形分隔开从该区域内的点观察第二个多边形被第一个遮挡。因此问题的核心转化为给定两个凸多边形求它们的两条内公切线。由于多边形顶点按顺时针顺序给出内公切线的方向与切点位置相关。直接枚举所有顶点对判断是否构成内公切线时间复杂度为O(NM)O(NM)O(NM)对于N,MN, MN,M可达10410^4104不可接受。需要利用凸多边形的性质采用线性时间的旋转卡壳算法。解题思路内公切线的旋转卡壳求法对于两个凸多边形AAA和BBB我们希望找到一条直线使得AAA的所有顶点均在该直线的一侧BBB的所有顶点均在另一侧。设f1f 1f1表示AAA在直线左侧即叉积≥0\ge 0≥0BBB在右侧叉积≤0\le 0≤0f−1f -1f−1表示AAA在右侧BBB在左侧。每次调用internalTangent(A, B, f)返回一对切点索引(i,j)(i, j)(i,j)表示直线过点A[i]A[i]A[i]和B[j]B[j]B[j]是一条内公切线。算法从初始指针i0,j0i 0, j 0i0,j0开始通过迭代调整指针直到直线满足条件。调整规则如下若BBB的前驱或后继顶点使得A[i]A[i]A[i]与B[j]B[j]B[j]的连线不满足BBB在−f-f−f侧的要求即叉积符号错误则推进jjj。若AAA的前驱或后继顶点使得B[j]B[j]B[j]与A[i]A[i]A[i]的连线不满足AAA在fff侧的要求则推进iii并标记更新。重复上述过程直到一次完整的扫描中没有任何指针被推进此时得到一条内公切线。最后需要处理共线退化的特殊情况当AAA的下一个顶点恰好在直线上时如果f1f1f1则将iii推进一个单位如果f−1f-1f−1则将iii退后一个单位。这是为了确保输出的切点不会导致后续顶点序列出现重复或遗漏。调用两次分别传入f1f1f1和f−1f-1f−1即可得到两条不同的内公切线。输出构建得到两条切线后第一条切线对应f1f1f1第二条对应f−1f-1f−1。输出时先输出第一条切线的斜率然后从第一个多边形上的第二个切点即第二条切线的AAA端顺时针遍历到第一个切点即第一条切线的AAA端包含两端所有顶点最后输出第二条切线的斜率。斜率计算时若两点横坐标相同则输出VERTICAL否则计算(y2-y1)/(x2-x1)保留三位小数。由于浮点数精度问题当斜率绝对值小于10−310^{-3}10−3时将其强制置为000以避免输出-0.000。复杂度分析每次调用internalTangent的指针移动总次数不超过O(NM)O(NM)O(NM)因此单次调用为线性复杂度。两次调用总时间复杂度为O(NM)O(NM)O(NM)空间复杂度为O(NM)O(NM)O(NM)完全满足题目要求。代码实现// Polygon Visibility// UVa ID: 746// Verdict: Accepted// Submission Date: 2026-07-07// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{intx,y;point(inta0,intb0):x(a),y(b){}pointoperator-(constpointo)const{returnpoint(x-o.x,y-o.y);}pointoperator(constpointo)const{returnpoint(xo.x,yo.y);}};longlongcross(point o,point a,point b){return1LL*(a.x-o.x)*(b.y-o.y)-1LL*(a.y-o.y)*(b.x-o.x);}pairint,intinternalTangent(vectorpointA,vectorpointB,intf){intn(int)A.size(),m(int)B.size();inti0,j0,update;do{update0;while(f*cross(A[i],B[j],B[(jm-1)%m])0||f*cross(A[i],B[j],B[(j1)%m])0){j(j1)%m;}while(f*cross(B[j],A[i],A[(in-1)%n])0||f*cross(B[j],A[i],A[(i1)%n])0){i(i1)%n;update1;}}while(update);if(f1cross(B[j],A[i],A[(i1)%n])0)i(i1)%n;if(f-1cross(B[j],A[i],A[(in-1)%n])0)i(in-1)%n;return{i,j};}voidtoSlope(point p,point q){intdxq.x-p.x,dyq.y-p.y;if(dx0)coutVERTICAL\n;else{doubleslope(double)dy/dx;if(fabs(slope)1e-3)slope0.0;coutfixedsetprecision(3)slope\n;}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,m,cases1;while(cinnm,nm){vectorpointA(n),B(m);for(inti0;in;i)cinA[i].xA[i].y;for(inti0;im;i)cinB[i].xB[i].y;auto[i1,j1]internalTangent(A,B,1);auto[i2,j2]internalTangent(A,B,-1);coutInstance cases:\n;toSlope(A[i1],B[j1]);intnowi1;do{coutA[now].x A[now].y\n;now(now1)%n;}while(now!i2);coutA[i2].x A[i2].y\n;toSlope(A[i2],B[j2]);}return0;}总结本题是计算几何中求凸多边形内公切线的典型应用。关键技巧在于旋转卡壳利用凸多边形的单调性在线性时间内完成切线搜索避免了平方级枚举。方向控制通过参数fff控制两个多边形分别位于直线两侧从而可求出两条不同的内公切线。共线处理切线可能经过多边形顶点需小心处理共线情况确保输出顺序正确。浮点数精度斜率输出时对绝对值小于10−310^{-3}10−3的值强制归零避免输出-0.000这是浮点运算中常见的陷阱。该解法同时具备时间高效性与实现稳健性是解决此类几何问题的标准方法。

UVa 746 Polygon Visibility

相关推荐

可白嫖源码---课程设计--毕业设计--springboot四川特产销售系统[编号：project17519]（案例分析）

OneNET云平台-物联云平台搭建

PI-Desktop 安装教程：10 分钟装好并跑通第一个 AI 编程任务

更多资讯

Windows XP IIS 5.1 安装全指南：i386源配置与元数据库修复

2026年AI+制造业应用全景与关键技术解析

Redis安装与配置全指南：从入门到生产环境部署

展厅中控系统TCP协议层鲁棒性设计与实战

AI安全新挑战：Mythos模型的风险与防护实践

.NET 5 WinForm免注册调用大漠插件实战指南

今日更新

学生选课系统DFD图绘制指南：边界划分与分层校验实战

JIRA敏捷落地：Scrum角色权限、Sprint与燃尽图避坑指南

SEMI S8人机工程验收实战：从条款拆解到现场实测的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？