题解：P11370 [Ynoi2024] 堕天作战/虚空处刑
Union_of_Britain · · 题解
把多边形和询问挂在 x 轴建立的线段树结构上的 log 个节点上。这样对于询问 A 和边 B 的交点
在祖先的节点
如果 A 是 B 的祖先，那么所有边被视为直线，询问是一般线段。而多边形的边不在端点以外位置相交，因此这些“直线”是具有上下关系的，排序二分即可找到询问点是否被直线划开。这一部分，对边在区间分出的 log 个节点中插入，询问在分出的 log 个节点及其祖先（显然这也是
反之 B 是 A 的祖先，即查询视为直线，边为线段。首先全局询问有方法是建多边形凸包，和凸包有交说明有交否则无交。然而这要求全局线段联通，所以还需更细致的讨论。
在这里的方法是把线段连通成的图形分为三种：只和
考虑只和左边有交的：照样算出区间
代码实现是非常繁琐的，还有点卡常（不知道标算如何做到那么快）。
这是一份（大概会被卡成 ~ 80 分的）参考代码，如果你希望知道这份代码的实现细节可以私信等等。后面卡常就是尽量减少
#include<bits/stdc++.h>
using namespace std;
bool mst;
#define db double
// #define endl "\n"
const int maxn=2e5+5,N=3e4+5;
const db eps=1e-6,INF=1e18,eps2=1e-10;
struct pt{db x,y;};
pt operator +(pt A,pt B){return {A.x+B.x,A.y+B.y};}
pt operator -(pt A,pt B){return {A.x-B.x,A.y-B.y};}
db operator *(pt A,pt B){return A.x*B.x+A.y*B.y;}
db operator ^(pt A,pt B){return A.x*B.y-A.y*B.x;}
#define Poly vector<pt>
pt a[maxn];int n,q,VV=3e4+1;
pt qp[maxn],qq[maxn];int qres[maxn];
int mmn=VV+1,mmx=0;
struct line{pt p,q;};
inline int dcmp(db x){return (x>eps)-(x<-eps);}
inline int dcmp2(db x){return (x>eps2)-(x<-eps2);}
inline bool operator <(line A,line B){return dcmp(A.p.y-B.p.y)!=0?A.p.y<B.p.y:A.q.y<B.q.y;}
inline bool pd1(line L,pt A){return dcmp((A.x-L.p.x)*(L.q.y-L.p.y)-(A.y-L.p.y)*(L.q.x-L.p.x))<=0;}
inline bool pd2(line L,pt A){return dcmp((A.x-L.p.x)*(L.q.y-L.p.y)-(A.y-L.p.y)*(L.q.x-L.p.x))<0;}
inline line getL(line L,db l,db r){
if(L.p.x==L.q.x)return L;
pt p={l,1.0*(l-L.p.x)/(L.q.x-L.p.x)*(L.q.y-L.p.y)+L.p.y};
pt q={r,1.0*(r-L.p.x)/(L.q.x-L.p.x)*(L.q.y-L.p.y)+L.p.y};
return {dcmp(L.p.x-l)>=0?L.p:p,dcmp(r-L.q.x)>=0?L.q:q};
}
ostream & operator<<(ostream &o, const pt &p){o<<"["<<p.x<<" , "<<p.y<<"]";return o;}
ostream & operator<<(ostream &o, const line &L){o<<"{"<<L.p<<" , "<<L.q<<"}";return o;}
ostream & operator<<(ostream &o, const Poly &A){o<<"{";for(int i=0;i<A.size();i++){if(i!=A.size()-1)o<<A[i]<<" , ";else o<<A[i];}o<<"}";return o;}
ostream & operator<<(ostream &o, const vector<db> &A){o<<"{";for(int i=0;i<A.size();i++){if(i!=A.size()-1)o<<A[i]<<" , ";else o<<A[i];}o<<"}";return o;}
namespace PHS{
line L[maxn];int tot=0;
inline void ins(line A){L[++tot]=A;}void clear(){tot=0;}void predo(){sort(L+1,L+tot+1);}
inline int pre1(pt p){
int l=1,r=tot,res=0;
while(l<=r){
int mid=l+r>>1;
if(pd1(L[mid],p))res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
inline int pre2(pt p){
int l=1,r=tot,res=0;
while(l<=r){
int mid=l+r>>1;
if(pd2(L[mid],p))res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
inline bool pd(pt p,pt q){
int A=pre2(p);
int B=A;while(B+1<=tot&&pd1(L[B+1],p))++B;if(B!=A)return 1;
int C=pre2(q);if(C!=B)return 1;
int D=C;while(D+1<=tot&&pd1(L[D+1],q))++D;if(D!=C)return 1;
return 0;
}
}
namespace SOLVE1{
vector<int> I[N<<2],E[N<<2];
namespace STS1{
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
inline void ins(int k,int l,int r,int x,int y,int u){
if(x>y)return ;
if(x<=l&&r<=y){
I[k].push_back(u);
return ;
}
if(x<=mid)ins(ls,l,mid,x,y,u);
if(mid<y)ins(rs,mid+1,r,x,y,u);
}
inline void ask(int k,int l,int r,int x,int y,int u){
if(E[k].empty()||E[k].back()!=u)E[k].push_back(u);
if((x<=l&&r<=y)||l==r)return ;
if(x<=mid)ask(ls,l,mid,x,y,u);
if(mid<y)ask(rs,mid+1,r,x,y,u);
}
inline void calc(int k,int l,int r){
PHS::clear();
for(auto i:I[k]){
pt p=a[i],q=(i==n?a[1]:a[i+1]);
if(p.x>q.x)swap(p,q);line L={p,q};
PHS::ins(getL(L,l-1,r));
}
PHS::predo();
for(auto u:E[k]){
if(qres[u])continue;
line G=getL((line){qp[u],qq[u]},l-1,r);
qres[u]|=PHS::pd(G.p,G.q);
}
if(l==r)return ;
calc(ls,l,mid),calc(rs,mid+1,r);
}
}
inline void solve1(){
for(int i=1;i<=n;i++){
pt p=a[i],q=(i==n?a[1]:a[i+1]);
if(p.x>q.x)swap(p,q);line L={p,q};
STS1::ins(1,mmn+1,mmx,p.x+1,q.x,i);
}
for(int i=1;i<=q;i++){
if(qp[i].x+1<=qq[i].x)STS1::ask(1,mmn+1,mmx,qp[i].x+1,qq[i].x,i);
STS1::ask(1,mmn+1,mmx,qq[i].x+1,qq[i].x+1,i);
STS1::ask(1,mmn+1,mmx,qp[i].x,qp[i].x,i);
}
STS1::calc(1,mmn+1,mmx);
}
}
inline db atan2(pt A){return atan2(A.y,A.x);}
inline db len(pt A){return A.x*A.x+A.y*A.y;}
inline db dis(pt A,pt B){return len(B-A);}
pt DC;int stk[maxn],tp;db pra[maxn],prd[maxn];pt cp[maxn];int per[maxn];
inline bool cmpp(int x,int y){
db sa=pra[x],sb=pra[y];
if(dcmp2(sa-sb)==0)return prd[x]<prd[y];
else return sa<sb;
}
inline db slope(pt x,pt y){
if(dcmp(x.x-y.x)==0)return dcmp(y.y-x.y)<=0?-INF:INF;
return (y.y-x.y)/(y.x-x.x);
}
namespace SOLVE2{
Poly Convex(Poly p){int n=p.size();
int C=0;for(int i=1;i<n;i++)if((dcmp(p[i].y-p[C].y)==0&&p[i].x<p[C].x)||dcmp(p[i].y-p[C].y)==-1)C=i;
swap(p[C],p[0]);DC=p[0];for(int i=0;i<n;i++)cp[i]=p[i],per[i]=i;
for(int i=1;i<n;i++)pra[i]=atan2(p[i]-DC),prd[i]=dis(p[i],DC);
sort(per+1,per+n,cmpp);for(int i=1;i<n;i++)p[i]=cp[per[i]];
stk[tp=1]=0;for(int i=1;i<n;i++){
while(tp>1&&((p[i]-p[stk[tp-1]])^(p[stk[tp]]-p[stk[tp-1]]))>=0)--tp;
stk[++tp]=i;
}Poly N;for(int i=1;i<=tp;i++)N.push_back(p[stk[i]]);return N;
}
int vis[maxn<<1];
db curL,curR;
vector<int> te[maxn<<1];
vector<Poly> PM;
Poly PPM[maxn],PU[maxn],PD[maxn];
vector<db> PUK[maxn],PDK[maxn];
pair<pair<db,db>,int> PML[maxn],PMR[maxn];
pair<db,int> lq[maxn],rq[maxn];int revL[maxn],revR[maxn];
line cline[maxn];
Poly CP[maxn];db CPL[maxn],CPR[maxn];int tot=0;
Poly CPcur,CPN;vector<db> CKcur,CKN;
inline Poly Standard(Poly A){
db mx=-INF;int p;
for(int i=0;i<A.size();i++){auto [x,y]=A[i];if(dcmp(x-curL)==0){if(dcmp(y-mx)>=0)mx=y,p=i;}}
Poly B={A[p]};int y=p;p=(p==0?A.size()-1:p-1);while(p!=y)B.push_back(A[p]),p=(p==0?(int)A.size()-1:p-1);
return B;
}
inline vector<db> calcCK(Poly A){
vector<db> res;int c=A.size()-1;
while(c>=1&&A[c].x<A[c-1].x)res.push_back(-slope(A[c-1],A[c])),--c;
reverse(res.begin(),res.end());
return res;
}
inline void merge(){
int c=CPcur.size()-1;int ptl=CPN.size();
for(int i=CPN.size()-1;i>=0;i--){
while(c>0&&dcmp((CPN[i]-CPcur[c])^(CPcur[c-1]-CPcur[c]))>=0){
if(CPcur[c].x<CPcur[c-1].x)CKcur.pop_back();--c;}
ptl=i;if(i>0&&dcmp((CPN[i]-CPcur[c])^(CPN[i-1]-CPcur[c]))<=0)break;
}
while(CPcur.size()-1>c)CPcur.pop_back();
vector<db> ccb;
for(int i=ptl;i<CPN.size();i++){
CPcur.push_back(CPN[i]);
int S=CPcur.size();
if(CPcur[S-1].x<CPcur[S-2].x)CKcur.push_back(-slope(CPcur[S-2],CPcur[S-1]));
}
}
inline bool cpd(line A){
if(CKcur.empty())return 0;
db K=(A.q.y-A.p.y)/(A.q.x-A.p.x);
int p=lower_bound(CKcur.begin(),CKcur.end(),-K)-CKcur.begin();
p=CKcur.size()-p-1;db mn=INF;
for(int j=(int)CPcur.size()-(p+3);j<(int)CPcur.size()-(p-3);j++)if(0<=j&&j<CPcur.size())mn=min(mn,CPcur[j].y-CPcur[j].x*K);
mn+=curL*K;if(dcmp(A.p.y-mn)>=0)return 1;return 0;
}
vector<pt> V;vector<pair<int,int> > E;
int st[maxn];int ct=0;vector<int> sdv;
vector<int> Spt[maxn];int cs=0;
vector<int> cpt;
struct PPHS{
vector<pair<line,int> > CQ;
int L,R;vector<int> H;
inline void insL(int i){
pair<pt,int> P={a[i],i},Q=(i==n?(pair<pt,int>){a[1],1}:(pair<pt,int>){a[i+1],i+1});
if(P.first.x>Q.first.x)swap(P,Q);line cd={P.first,Q.first};
line cda=getL(cd,L,R);int u,v;
if(dcmp(P.first.x-L)>=0){if(!st[P.second])st[P.second]=++ct,sdv.push_back(P.second),V.push_back(a[P.second]);u=st[P.second]-1;}
else V.push_back(cda.p),++ct,u=ct-1;
if(dcmp(R-Q.first.x)>=0){if(!st[Q.second])st[Q.second]=++ct,sdv.push_back(Q.second),V.push_back(a[Q.second]);v=st[Q.second]-1;}
else V.push_back(cda.q),++ct,v=ct-1;
E.push_back({u,v});
}
inline void predo(){
for(auto x:sdv)st[x]=0;sdv.clear();
E.clear();ct=0;V.clear();
for(auto x:H)insL(x);
}
inline void DFS(int u){
if(vis[u])return ;
cpt.push_back(u);vis[u]=1;
for(auto v:te[u])DFS(v);
}
inline int Pre(int u,int i){i--;if(i==-1)i=PPM[u].size()-1;return i;}
inline int Suf(int u,int i){i++;if(i==PPM[u].size())i=0;return i;}
inline void solvecon(int u){
int x=0;while(PPM[u][x].x>=PPM[u][Pre(u,x)].x)x=Pre(u,x);
PU[u].clear(),PD[u].clear();PD[u].push_back(PPM[u][x]);
int y=x;PDK[u].clear(),PUK[u].clear();
while(PPM[u][x].x<=PPM[u][Suf(u,x)].x)x=Suf(u,x),PD[u].push_back(PPM[u][x]);
PU[u].push_back(PPM[u][x]);x=Suf(u,x);while(x!=y)PU[u].push_back(PPM[u][x]),x=Suf(u,x);
PU[u].push_back(PPM[u][y]);
for(int i=0;i<PU[u].size()-1;i++)PUK[u].push_back(slope(PU[u][i+1],PU[u][i]));
for(int i=0;i<PD[u].size()-1;i++)PDK[u].push_back(slope(PD[u][i],PD[u][i+1]));
}
inline db AskU(db K,int u){
db mx=-INF;
int p=lower_bound(PUK[u].begin(),PUK[u].end(),K)-PUK[u].begin();
for(int i=p-3;i<=p+3;i++)if(0<=i&&i<PU[u].size())mx=max(mx,PU[u][i].y-PU[u][i].x*K);
return mx;
}
inline db AskD(db K,int u){
db mn=INF;
int p=lower_bound(PDK[u].begin(),PDK[u].end(),K)-PDK[u].begin();
for(int i=p-3;i<=p+3;i++)if(0<=i&&i<PD[u].size())mn=min(mn,PD[u][i].y-PD[u][i].x*K);
return mn;
}
inline void calc(){curL=L,curR=R;
PM.clear();
for(int i=1;i<=cs;i++){
cpt=Spt[i];int lc=0,rc=0;
Poly ccpt;for(auto x:cpt)ccpt.push_back(V[x]);
for(auto x:cpt)lc+=(dcmp(V[x].x-L)==0),rc+=(dcmp(V[x].x-R)==0);
if(lc&&!rc)PM.push_back(ccpt);
}
int S=PM.size();
if(!S)return ;
for(int i=0;i<PM.size();i++){
auto X=PM[i];db mn=INF,mx=-INF;
for(auto [x,y]:X)if(dcmp(x-L)==0)mn=min(mn,y),mx=max(mx,y);
PML[i]={{mn,mx},i};
}
sort(PML,PML+S);db cmn=-INF,cmx=-INF;
vector<int> cur;for(int i=1;i<=tot;i++)CP[i].clear();tot=0;
for(int i=0;i<S;i++){
if(dcmp(PML[i].first.second-cmx)<=0)continue;
if(dcmp(PML[i].first.first-cmx)>0){
if(cur.size()){++tot;for(auto x:cur){for(auto y:PM[x])CP[tot].push_back(y);}CPL[tot]=cmn,CPR[tot]=cmx;}
cur={PML[i].second};cmn=PML[i].first.first;cmx=PML[i].first.second;
}else cur.push_back(PML[i].second),cmx=PML[i].first.second;
}
if(cur.size()){++tot;for(auto x:cur){for(auto y:PM[x])CP[tot].push_back(y);}CPL[tot]=cmn,CPR[tot]=cmx;}
for(int i=1;i<=tot;i++)CP[i]=Standard(Convex(CP[i]));
int cnt=0;
for(auto [L,u]:CQ)if(!qres[u])lq[++cnt]={L.p.y,u};sort(lq+1,lq+cnt+1);CPcur.clear(),CKcur.clear();
int cl=1;
reverse(CPL+1,CPL+tot+1);reverse(CPR+1,CPR+tot+1);
reverse(CP+1,CP+tot+1);reverse(lq+1,lq+cnt+1);CPR[tot+1]=-INF;
for(int i=1;i<=tot+1;i++){
while(cl<=cnt&&dcmp(lq[cl].first-CPR[i])>0){if(!qres[lq[cl].second])qres[lq[cl].second]|=cpd(cline[lq[cl].second]);++cl;}
while(cl<=cnt&&dcmp(lq[cl].first-CPL[i])>=0&&dcmp(lq[cl].first-CPR[i])<=0)qres[lq[cl].second]=1,++cl;
if(i<=tot){
if(i==1)CPcur=CP[i],CKcur=calcCK(CP[i]);
else CPN=CP[i],CKN=calcCK(CP[i]),merge();
}
}
}
inline void solve(){
predo();vector<pair<line,int> > NCQ;
for(auto [L,u]:CQ)if(!qres[u])NCQ.push_back({L,u});
swap(CQ,NCQ);if(!CQ.size()||!E.size())return ;
for(int i=0;i<V.size();i++)vis[i]=0,te[i].clear();
for(auto [u,v]:E)te[u].push_back(v),te[v].push_back(u);
PM.clear();cs=0;
for(int i=0;i<V.size();i++){
if(vis[i])continue;
cpt.clear();DFS(i);int lc=0,rc=0;Spt[++cs]=cpt;
Poly ccpt;for(auto x:cpt)ccpt.push_back(V[x]);
for(auto x:cpt){
if(dcmp(V[x].x-L)==0)lc++;
if(dcmp(V[x].x-R)==0)rc++;
}
if(lc&&rc)PM.push_back(ccpt);
}int S=PM.size();int cnt=0;
for(auto x:PM)PPM[cnt++]=Convex(x);
for(int i=0;i<S;i++){
db mn=VV+1,mx=0;auto X=PM[i];
for(auto x:X)if(dcmp(x.x-L)==0)mn=min(mn,x.y),mx=max(mx,x.y);
PML[i]={{mn,mx},i};
}
for(int i=0;i<S;i++){
db mn=VV+1,mx=0;auto X=PM[i];
for(auto x:X)if(dcmp(x.x-R)==0)mn=min(mn,x.y),mx=max(mx,x.y);
PMR[i]={{mn,mx},i};
}int SQ=0;
sort(PML,PML+S);sort(PMR,PMR+S);
for(int i=0;i<S;i++)solvecon(i);
for(auto [L,i]:CQ){
auto [p,q]=L;
lq[SQ]={p.y,i},rq[SQ]={q.y,i};
++SQ;
}
sort(lq,lq+SQ);sort(rq,rq+SQ);
int cl=0,cr=0;
for(int i=0;i<SQ;i++)revL[lq[i].second]=revR[rq[i].second]=S;
for(int i=0;i<S;i++){
auto [P,id]=PML[i];
auto [l,r]=P;
while(cl<SQ&&dcmp(lq[cl].first-l)<0)revL[lq[cl].second]=i,++cl;
while(cl<SQ&&dcmp(lq[cl].first-l)>=0&&dcmp(r-lq[cl].first)>=0)qres[lq[cl].second]=1,++cl;
}
for(int i=0;i<S;i++){
auto [P,id]=PMR[i];
auto [l,r]=P;
while(cr<SQ&&dcmp(rq[cr].first-l)<0)revR[rq[cr].second]=i,++cr;
while(cr<SQ&&dcmp(rq[cr].first-l)>=0&&dcmp(r-rq[cr].first)>=0)qres[rq[cr].second]=1,++cr;
}
for(auto [Li,i]:CQ){
if(qres[i])continue;
if(revL[i]!=revR[i])qres[i]=1;
else{
auto [p,q]=Li;
db K=slope(p,q);
pair<db,db> I1={-INF,INF},I2={-INF,INF};
if(revL[i]>0){
auto r=AskU(K,PML[revL[i]-1].second);
r+=L*K;
if(dcmp(r-p.y)>=0)qres[i]=1;
}
if(revL[i]<S){
auto l=AskD(K,PML[revL[i]].second);
l+=L*K;
if(dcmp(p.y-l)>=0)qres[i]=1;
}
}
}
for(auto [L,u]:CQ)cline[u]=L;calc();
for(auto &u:V)u.x=L+R-u.x;
for(int i=0;i<CQ.size();i++)swap(CQ[i].first.p.y,CQ[i].first.q.y);
for(auto [L,u]:CQ)cline[u]=L;calc();
for(auto &u:V)u.x=L+R-u.x;
for(int i=0;i<CQ.size();i++)swap(CQ[i].first.p.y,CQ[i].first.q.y);
for(auto &u:V)u.y=VV-u.y;
for(int i=0;i<CQ.size();i++)CQ[i].first.p.y=VV-CQ[i].first.p.y,CQ[i].first.q.y=VV-CQ[i].first.q.y;
for(auto [L,u]:CQ)cline[u]=L;calc();
for(auto &u:V)u.x=L+R-u.x;
for(int i=0;i<CQ.size();i++)swap(CQ[i].first.p.y,CQ[i].first.q.y);
for(auto [L,u]:CQ)cline[u]=L;calc();
}
}F[N<<2];
namespace STS2{
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
inline void ins(int k,int l,int r,int x,int y,int u){
if(y<l||x>r)return ;
if(F[k].H.empty()||F[k].H.back()!=u)F[k].H.push_back(u);
if((x<=l&&r<=y)||(l==r))return ;
if(x<=mid)ins(ls,l,mid,x,y,u);
if(mid<y)ins(rs,mid+1,r,x,y,u);
}
inline void ask(int k,int l,int r,int x,int y,line L,int u){
if(x<=l&&r<=y){F[k].CQ.push_back({getL(L,l-1,r),u});return ;}
if(l==r)return ;
if(x<=mid)ask(ls,l,mid,x,y,L,u);
if(mid<y)ask(rs,mid+1,r,x,y,L,u);
}
inline void calc(int k,int l,int r){
F[k].L=l-1,F[k].R=r,F[k].solve();
if(l==r)return ;
calc(ls,l,mid);calc(rs,mid+1,r);
}
}
inline void solve2(){
for(int i=1;i<=n;i++){
pt P=a[i],Q=(i==n?a[1]:a[i+1]);
if(P.x>Q.x)swap(P,Q);
if(P.x<Q.x)STS2::ins(1,mmn+1,mmx,P.x+1,Q.x,i);
else STS2::ins(1,mmn+1,mmx,P.x,P.x,i),STS2::ins(1,mmn+1,mmx,Q.x+1,Q.x+1,i);
}
for(int i=1;i<=q;i++){
if(qres[i])continue;
pt p=qp[i],q=qq[i];
STS2::ask(1,mmn+1,mmx,p.x+1,q.x,(line){p,q},i);
}
STS2::calc(1,mmn+1,mmx);
}
}
namespace SOLVE3{
namespace ST{
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
int xds[N<<2],add[N<<2];
inline void ADD(int k,int v){xds[k]+=v,add[k]+=v;}
inline void pushdown(int k){ADD(ls,add[k]),ADD(rs,add[k]),add[k]=0;}
inline void pushup(int k){xds[k]=max(xds[ls],xds[rs]);}
inline void modify(int k,int l,int r,int x,int y,int v){
if(x<=l&&r<=y)return ADD(k,v);
pushdown(k);if(x<=mid)modify(ls,l,mid,x,y,v);
if(mid<y)modify(rs,mid+1,r,x,y,v);pushup(k);
}
inline int query(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return xds[k];
int res=0;pushdown(k);
if(x<=mid)res=max(res,query(ls,l,mid,x,y));
if(mid<y)res=max(res,query(rs,mid+1,r,x,y));
return res;
}
}
vector<array<int,3> > e[N];
vector<array<int,3> > re[N];
inline void solve3(){
for(int i=1;i<=n;i++){
pt P=a[i],Q=(i==n?a[1]:a[i+1]);
if(dcmp(P.x-Q.x)==0){int L=(min(P.y,Q.y)+0.5),R=(max(P.y,Q.y)+0.5);e[(int)(P.x+0.5)].push_back({L,R,-1});}
}
for(int i=1;i<=q;i++){
pt P=qp[i],Q=qq[i];
if(dcmp(P.x-Q.x)==0){int L=(min(P.y,Q.y)+0.5),R=(max(P.y,Q.y)+0.5);re[(int)(P.x+0.5)].push_back({L,R,i});}
}
for(int i=0;i<=VV;i++){
for(auto [l,r,id]:e[i])ST::modify(1,0,VV,l,r,1);
for(auto [l,r,id]:re[i])qres[id]|=(ST::query(1,0,VV,l,r)>0);
for(auto [l,r,id]:e[i])ST::modify(1,0,VV,l,r,-1);
}
}
}
unordered_set<int> ST;
bool med;
signed main(){
cin>>n>>q;
cerr<<(&mst-&med)/1024.0/1024.0<<endl;
for(int i=1;i<=n;i++){
int cx,cy;cin>>cx>>cy;
a[i].x=cx,a[i].y=cy,mmx=max(mmx,(int)a[i].x),mmn=min(mmn,(int)a[i].x);
ST.insert(cx*N+cy);
}
for(int i=1;i<=q;i++){
int a,b,c,d;cin>>a>>b>>c>>d;
qp[i].x=a,qp[i].y=b,qq[i].x=c,qq[i].y=d;
if(ST.count(a*N+b)||ST.count(c*N+d))qres[i]=1;
if(qp[i].x>=qq[i].x)swap(qp[i],qq[i]);
line Q={qp[i],qq[i]};if(qq[i].x<mmn||qp[i].x>mmx)qres[i]=2;
else Q=getL(Q,mmn,mmx);
qp[i]=Q.p,qq[i]=Q.q;
}
SOLVE3::solve3();SOLVE1::solve1();SOLVE2::solve2();
for(int i=1;i<=q;i++){
if(qres[i]==1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}