题目描述

给定两个互不相交的凸多边形（非退化），多边形顶点按顺时针顺序给出。需要求平面上所有点PPP（PPP不在第一个多边形内部）的集合，使得存在QQQ属于第二个多边形，且线段PQ‾\overline{PQ}PQ​的内部与第一个多边形相交。该集合的边界由两条无限直线以及第一个多边形上的一段有限线段组成。要求输出这两条无限直线的斜率（若为垂直直线则输出VERTICAL），以及第一个多边形上构成有限线段的所有顶点，且顶点按顺时针顺序给出。

输入格式

每个测试用例包含以下内容：

• 第一行：两个正整数NNN和MMM（3≤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的所有顶点均在另一侧。设f=1f = 1f=1表示AAA在直线左侧（即叉积≥0\ge 0≥0），BBB在右侧（叉积≤0\le 0≤0）；f=−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]是一条内公切线。

算法从初始指针i=0,j=0i = 0, j = 0i=0,j=0开始，通过迭代调整指针，直到直线满足条件。调整规则如下：

• 若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的下一个顶点恰好在直线上时，如果f=1f=1f=1，则将iii推进一个单位；如果f=−1f=-1f=−1，则将iii退后一个单位。这是为了确保输出的切点不会导致后续顶点序列出现重复或遗漏。

调用两次，分别传入f=1f=1f=1和f=−1f=-1f=−1，即可得到两条不同的内公切线。

输出构建

得到两条切线后，第一条切线对应f=1f=1f=1，第二条对应f=−1f=-1f=−1。输出时，先输出第一条切线的斜率，然后从第一个多边形上的第二个切点（即第二条切线的AAA端）顺时针遍历到第一个切点（即第一条切线的AAA端），包含两端所有顶点，最后输出第二条切线的斜率。

斜率计算时，若两点横坐标相同，则输出VERTICAL；否则计算(y2-y1)/(x2-x1)，保留三位小数。由于浮点数精度问题，当斜率绝对值小于10−310^{-3}10−3时，将其强制置为000，以避免输出-0.000。

复杂度分析

每次调用internalTangent的指针移动总次数不超过O(N+M)O(N+M)O(N+M)，因此单次调用为线性复杂度。两次调用总时间复杂度为O(N+M)O(N+M)O(N+M)，空间复杂度为O(N+M)O(N+M)O(N+M)，完全满足题目要求。

代码实现

// Polygon Visibility// UVa ID: 746// Verdict: Accepted// Submission Date: 2026-07-07// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structpoint{intx,y;point(inta=0,intb=0):x(a),y(b){}pointoperator-(constpoint&o)const{returnpoint(x-o.x,y-o.y);}pointoperator+(constpoint&o)const{returnpoint(x+o.x,y+o.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);}pair<int,int>internalTangent(vector<point>&A,vector<point>&B,intf){intn=(int)A.size(),m=(int)B.size();inti=0,j=0,update;do{update=0;while(f*cross(A[i],B[j],B[(j+m-1)%m])>0||f*cross(A[i],B[j],B[(j+1)%m])>0){j=(j+1)%m;}while(f*cross(B[j],A[i],A[(i+n-1)%n])>0||f*cross(B[j],A[i],A[(i+1)%n])>0){i=(i+1)%n;update=1;}}while(update);if(f==1&&cross(B[j],A[i],A[(i+1)%n])==0)i=(i+1)%n;if(f==-1&&cross(B[j],A[i],A[(i+n-1)%n])==0)i=(i+n-1)%n;return{i,j};}voidtoSlope(point p,point q){intdx=q.x-p.x,dy=q.y-p.y;if(dx==0)cout<<"VERTICAL\n";else{doubleslope=(double)dy/dx;if(fabs(slope)<1e-3)slope=0.0;cout<<fixed<<setprecision(3)<<slope<<'\n';}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,m,cases=1;while(cin>>n>>m,n&&m){vector<point>A(n),B(m);for(inti=0;i<n;++i)cin>>A[i].x>>A[i].y;for(inti=0;i<m;++i)cin>>B[i].x>>B[i].y;auto[i1,j1]=internalTangent(A,B,1);auto[i2,j2]=internalTangent(A,B,-1);cout<<"Instance "<<cases++<<":\n";toSlope(A[i1],B[j1]);intnow=i1;do{cout<<A[now].x<<" "<<A[now].y<<"\n";now=(now+1)%n;}while(now!=i2);cout<<A[i2].x<<" "<<A[i2].y<<"\n";toSlope(A[i2],B[j2]);}return0;}

总结

本题是计算几何中求凸多边形内公切线的典型应用。关键技巧在于：

• 旋转卡壳：利用凸多边形的单调性，在线性时间内完成切线搜索，避免了平方级枚举。
• 方向控制：通过参数fff控制两个多边形分别位于直线两侧，从而可求出两条不同的内公切线。
• 共线处理：切线可能经过多边形顶点，需小心处理共线情况，确保输出顺序正确。
• 浮点数精度：斜率输出时，对绝对值小于10−310^{-3}10−3的值强制归零，避免输出-0.000，这是浮点运算中常见的陷阱。

该解法同时具备时间高效性与实现稳健性，是解决此类几何问题的标准方法。