要点不多，记一下即可。
\(G\) 的对偶图记为 \(G^*\)。
-
\(G^*\) 为连通图，若 \(G\) 联通，则 \(G^{*}{^*}=G\)
-
\(G^*\) 中的简单环对应着 \(G\) 中的极小割，（简单对应极小），利用该性质，可以把平面图上的最小割问题转化为对偶图上的最短路问题
-
平面图欧拉公式：\(V-E+F-C=1\)，点数-边数+面数-联通块数=1
-
平面图规模上限：\(E\le 3\times V-6,F\le 2\times V-4\)
-
平面图点定位：使用扫描线+set 即可，实现不难，有点细节
-
平面图求对偶图：对于每个点的出边极角排序即可
n 合 1 模板题：link
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10,K=__lg(N)+2,INF=1e9+1;
int q,V,E,F;
struct vec{
int x,y;
}a[N];
vec operator - (const vec &a,const vec &b){
return {a.x-b.x,a.y-b.y};
}
bool operator == (const vec &a,const vec &b){
return a.x==b.x&&a.y==b.y;
}
int find(const vec &a){
if(!a.y)return a.x>0?0:1;
return a.y>0?0:1;
}
ll cross(const vec &a,const vec &b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
bool operator < (const vec &a,const vec &b){
int x=find(a),y=find(b);
return x^y?x<y:cross(a,b)>0;
}
struct edges{
int v,w,id,to,nex;
}edge[N*2];
int kk=1,head[N];
void add(int u,int v,int w){
edge[++kk]={v,w,0,0,head[u]},head[u]=kk;
edge[++kk]={u,w,0,0,head[v]},head[v]=kk;
}
void read(int &x){
char c;
for(x=0;!isdigit(c=getchar()););
for(;x=x*10+c-'0',isdigit(c=getchar()););
if(x<<=1,c=='.')getchar(),x++;
}
struct edgs{
int u,v,w;
};
vector<edgs>edg;
namespace DSU{
int fa[N];
void init(int n){
iota(fa,fa+1+n,0);
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return 0;
return fa[x]=y,1;
}
}
vector<pair<int,int> >to[N];
void Add(int u,int v,int w){
to[u].push_back({v,w}),to[v].push_back({u,w});
}
int dep[N],anc[K][N],mx[K][N];
#define v e.first
#define w e.second
void dfs1(int u,int fa=0){
anc[0][u]=fa,dep[u]=dep[fa]+1;
for(auto e:to[u])if(v^fa)mx[0][v]=w,dfs1(v,u);
}
#undef v
#undef w
int query(int u,int v){
if(!~u||!~v)return INF;
if(dep[u]<dep[v])swap(u,v);
int ans=0;
for(int x=dep[u]-dep[v];x;x^=x&-x){
int i=__builtin_ctz(x);
ans=max(ans,mx[i][u]),u=anc[i][u];
}
if(u==v)return ans;
for(int i=__lg(dep[u]);~i;i--)
if(anc[i][u]^anc[i][v]){
ans=max({ans,mx[i][u],mx[i][v]});
u=anc[i][u],v=anc[i][v];
}
return max({ans,mx[0][u],mx[0][v]});
}
int s[N],t[N];
int cnt,buf[N];
int now;
using big=__int128;
struct line{
vec s,t;
int id;
big calc()const{
return (1ll*s.y*(t.x-now)+1ll*t.y*(now-s.x));
}
int len()const{
return t.x-s.x;
}
bool operator < (const line &x)const{
if(s==x.s)return cross(t-s,x.t-s)>0;
if(t==x.t)return cross(s-t,x.s-t)<0;
big tmp=calc()*x.len()-x.calc()*len();
if(tmp)return tmp<0;
return id<x.id;
}
};
set<line>S;
int k;
struct ques{
int x,y,*ans;
}o[N*2];
vector<int>p[N];
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&V,&E);
for(int i=1;i<=V;i++)read(a[i].x),read(a[i].y);
for(int i=1;i<=V;i++)buf[++cnt]=a[i].x;
sort(buf+1,buf+1+cnt),cnt=unique(buf+1,buf+1+cnt)-buf-1;
buf[cnt+1]=INF;
for(int i=1;i<=V;i++)p[lower_bound(buf+1,buf+1+cnt,a[i].x)-buf].push_back(i);
for(int i=1,u,v,w;i<=E;i++){
scanf("%d%d%d",&u,&v,&w),add(u,v,w);
}
int id=1;
for(int i=2;i<=V;i++)if(a[i].x>a[id].x)id=i;
for(int u=1;u<=V;u++){
vector<pair<int,int> >to;
for(int i=head[u];i;i=edge[i].nex)to.push_back({edge[i].v,i});
sort(to.begin(),to.end(),[&](pair<int,int>x,pair<int,int>y){
return a[x.first]-a[u]<a[y.first]-a[u];
});
if(u==id)edge[to[0].second].id=-1;
int len=to.size();
for(int i=0;i<len;i++)edge[to[i].second^1].to=to[(i+1)%len].second;
}
for(int u=1;u<=V;u++){
for(int i=head[u],j;i;i=edge[i].nex)if(!edge[i].id){
F++;
for(j=i;!edge[j].id;j=edge[j].to)edge[j].id=F;
if(!~edge[j].id){
for(F--,j=edge[j].to;~edge[j].id;j=edge[j].to)edge[j].id=-1;
}
}
}
// for(int u=1;u<=V;u++){
// for(int i=head[u];i;i=edge[i].nex){
// fprintf(stderr,"%d %d %d\n",u,edge[i].v,edge[i].id);
// }
// }
for(int i=2;i<=kk;i+=2){
if(~edge[i].id&&~edge[i+1].id)
edg.push_back({edge[i].id,edge[i+1].id,edge[i].w});
}
sort(edg.begin(),edg.end(),[](edgs x,edgs y){return x.w<y.w;});
DSU::init(F);
for(edgs x:edg)if(DSU::merge(x.u,x.v))Add(x.u,x.v,x.w);
for(int i=1;i<=F;i++)if(DSU::fa[i]==i)Add(0,i,INF);
dfs1(0);
for(int i=1;(1<<i)<=F;i++)
for(int u=1;u<=F;u++){
int t=anc[i-1][u];
anc[i][u]=anc[i-1][t];
mx[i][u]=max(mx[i-1][u],mx[i-1][t]);
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
int x,y;
read(x),read(y);
o[++k]={x,y,&s[i]};
read(x),read(y);
o[++k]={x,y,&t[i]};
}
sort(o+1,o+1+k,[](ques x,ques y){return x.x<y.x;});
for(int i=0,x=1;i<=cnt;i++){
now=buf[i];
for(int u:p[i]){
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
if(a[v].x<a[u].x)S.erase({a[v],a[u],edge[i^1].id});
}
}
for(int u:p[i]){
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
if(a[v].x>a[u].x)S.insert({a[u],a[v],edge[i].id});
}
}
for(;x<=k&&o[x].x>=buf[i]&&o[x].x<buf[i+1];x++){
vec p={o[x].x,o[x].y};
now=o[x].x;
auto it=S.lower_bound({p,{p.x+1,p.y},0});
if(it==S.end())*o[x].ans=-1;
else *o[x].ans=it->id;
}
}
for(int i=1;i<=q;i++){
int ans=query(s[i],t[i]);
if(ans>=INF)puts("-1");
else printf("%d\n",ans);
}
return 0;
}