【洛谷4073】[WC2013] 平面图（对偶图）

题目链接

• 给定一张 \(n\) 个点和 \(m\) 条边的平面图，每条边有一个边权。
• \(q\) 次询问，每次给定两个点，询问用一条曲线将它们相连所经最大边权的最小值，要求不能经过外平面。
• \(5\le n,m,q\le10^5\)

平面图求对偶图

这题其实是平面图对偶图相关的一些算法的模板题。（虽然感觉并不会考这种东西）

首先考虑如何求出平面图的对偶图。

先把一条无向边视作两条有向边，然后对每个点将它的所有出边极角排序，记下每条出边的下一条是谁。

任选一条边 \(x\rightarrow y\) 出发，然后选择 \(y\rightarrow x\) 的下一条边 \(y\rightarrow z\) 继续走，以此类推直至走回 \(x\)，这样绕出的一个环围出的面就是对偶图中的一个点。

得出点之后，对每条无向边，在它拆成的两条有向边各自相邻的对偶图中的点之间连边，边权就是这条无向边的边权。这样便建出了对偶图。

显然求点的过程中每条边只需要访问一次，因此这里的复杂度瓶颈实际上在于极角排序。

注意到这题中还存在一个限制，就是不能经过外平面。

发现按照这样走出的环如果围出的是外平面，环上的点将是按照逆时针顺序访问的；如果是内平面，则将是按照顺时针顺序访问的。

可以利用叉积计算有向面积的方式来判断访问顺序，从而判断围出的面是否为外平面。

平面图点定位

为了实现询问，需要判断询问给出的所有点分别在哪个面中，也即属于对偶图中的哪个点。

可以扫描线，用 set 维护当前存在的所有边的相对顺序。

那么对于每个点，只要 lower_bound 求出它上方的第一条边，那么它就处于这条边下面的那个面中。

Kruskal 重构树

其实也可以 MST+树上倍增。不过我还是选择了直接 Kruskal 重构树。

询问就是求两点在 Kruskal 重构树中 LCA 的权值。

代码：\(O(n\log n)\)

#include
#define Tp template
#define Ts template
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 100000
#define LG 18
#define DB double
#define add(x,y,z) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].v=z)
using namespace std;
int n,m,Qt,ee=1,lnk[N+5];struct edge {int to,nxt,v,g;}e[2*N+5];
struct P
{
	DB x,y;P(RI a=0,RI b=0):x(a),y(b){}
	I P operator - (Cn P& o) Cn {return P(x-o.x,y-o.y);}
	I DB operator ^ (Cn P& o) Cn {return x*o.y-y*o.x;}
	I friend bool operator < (Cn P& A,Cn P& B) {RI a=A.x>0||!A.x&&A.y<0,b=B.x>0||!B.x&&B.y<0;return a^b?a>b:(A^B)>0;}
}p[N+5],q[2*N+5],tmp[N+5];
bool cmp(CI x,CI y) {return tmp[e[x].to]ct&&(dfs(S[x][0]),dfs(S[x][1]),0);
	}
	I void Build()//建树
	{
		RI et=0,i;for(i=2;i<=ee;i+=2) bl[i]^Out&&bl[i^1]^Out&&(s[++et]=(edge){bl[i],bl[i^1],e[i].v},0);//存下所有边
		RI x,y;for(sort(s+1,s+et+1),Nt=ct,i=1;i<=et;++i)//Kruskal
			(x=Fa(s[i].x))^(y=Fa(s[i].y))&&(V[f[x][0]=f[y][0]=fa[x]=fa[y]=++Nt]=s[i].v,S[Nt][0]=x,S[Nt][1]=y);
		dfs(Nt);
	}
	I int LCA(RI x,RI y)//倍增LCA
	{
		RI i;for(D[x]>i&1&&(x=f[x][i]);if(x==y) return x;
		for(i=0;f[x][i]^f[y][i];++i);for(--i;~i;--i) f[x][i]^f[y][i]&&(x=f[x][i],y=f[y][i]);return f[x][0];
	}
	I int Q(CI x,CI y) {if(x==Out||y==Out) return -1;RI z=LCA(x,y);return z?V[z]:-1;}//询问
}
namespace Scan//扫描线实现点定位
{
	DB nw;struct line {int p;DB k,b;bool operator < (Cn line& o) Cn {return k*nw+b0.1?x G;I void Get()
	{
		RI i,j;line s;for(i=1;i<=n;++i) for(j=lnk[i];j;j=e[j].nxt) if(p[i].xp)//询问点，找到上方第一条线段
		for(i=1;i<=2*Qt;++i) id[i]=i;for(sort(id+1,id+2*Qt+1,cmp),sort(g+1,g+c+1),i=j=1;i<=c;++i)
		{
			W(j<=2*Qt&&q[id[j]].x