RT,大概思路是初始速度方向一定是某个线段端点到原点的方向(把询问点也看做线段),然后把这个方向旋转到垂直向下,之后排序线段树覆盖维护从一个线段滑下去之后下一步落在哪里。
WA on 5。qwq
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl "\n"
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
double eps=1e-9;
const double pi=acosl(-1);
class node{
public:
double x,y;
node(double X,double Y){
x=X,y=Y;
}
node(){
x=0,y=0;
}
friend node operator-(const node A,const node B){
return node(A.x-B.x,A.y-B.y);
}
friend double operator *(const node A,const node B){
return A.x*B.y-B.x*A.y;
}
inline node ROTA(double theta){
double C=cosl(theta),S=sinl(theta);
return node(x*C-y*S,x*S+y*C);
}
inline double THETA(){
if(len()==0)
return pi/2;
return atan2l(y,x);
}
};
class line{
public:
node S,T;
int oc;
int askid;
line(){
oc=0;
askid=0;
}
line(node A,node B,int OC=0,int id=0){
S=A,T=B,askid=id,oc=OC;
}
inline line ROTA(double theta){
return line(S.ROTA(theta),T.ROTA(theta),oc,askid);
}
inline void chk(){
if(S.x>T.x)swap(S,T);
}
inline double LOW(){
return min(S.y,T.y);
}
inline double HGH(){
return max(S.y,T.y);
}
inline double THETA(){
return (T-S).THETA();
}
}T[3010],P[3010];
bool ok[3010];
bool ANS[3010];
int w[6010<<2];
inline void pd(int x){
if(w[x]){
w[lc(x)]=w[rc(x)]=w[x];
w[x]=0;
}
}
inline void init(){memset(w,-1,sizeof(w));
}
int n,q;
inline void mod(int x,int l,int r,int L,int R,int p){
if(L<=l&&r<=R){
w[x]=p;
return ;
}
pd(x);
int mid=l+r>>1;
if(L<=mid)mod(lc(x),l,mid,L,R,p);
if(R>mid)mod(rc(x),mid+1,r,L,R,p);
return ;
}
inline int g(int x,int l,int r,int loc){
if(w[x])return w[x];
if(l==r)return w[x];
pd(x);
int mid=l+r>>1;
if(loc<=mid)return g(lc(x),l,mid,loc);
else return g(rc(x),mid+1,r,loc);
}
inline void mod(int l,int r,int id){
mod(1,1,2*n,min(l,r),max(l,r),id);
}
inline int g(int x){
return g(1,1,2*n,x);
}
double b[6030],*tmp;
inline bool cmp(line x,line y){
return x.LOW()<y.LOW();
}
inline bool chk(double theta){
while(theta>pi)theta-=pi;
while(theta<0)theta+=pi;
return pi/4<theta&&theta<pi*3/4;
}
inline int rk(double x){
return lower_bound(b+1,tmp,x)-b;
}
int NOW=0;
int c=0;
inline void UN(){
tmp=b+2;
for(int i=2;i<=c;i++)
if(abs(*tmp-b[i])>eps)
++tmp,*tmp=b[i];
else *tmp=b[i];
}
inline void calc(double theta){
c=0;
// cout<<theta<<" "<<pi<<endl<<endl;
for(int i=1;i<=n;i++)
P[i]=T[i].ROTA(theta),b[++c]=P[i].S.x,b[++c]=P[i].T.x,P[i].chk()
// ,cout<<P[i].oc<<" "<<P[i].THETA()<<" "<<P[i].S.x<<" "<<P[i].T.x<<endl<<endl
;
init();
sort(b+1,b+c+1);
sort(P+1,P+n+1,cmp);
UN();
bool e=0;
for(int i=1;i<=n;i++){
if(P[i].HGH()<0)continue;
if(P[i].LOW()<0&&(P[i].T-P[i].S)*(node(0,0)-P[i].S)>0)continue;
// cout<<P[i].S.x<<" "<<P[i].S.y<<" "<<P[i].T.x<<" "<<P[i].T.y<<" "<<P[i].THETA()<<endl;
// cout<<P[i].oc<<" "<<rk(P[i].S.x)<<" "<<rk(P[i].T.x)<<endl;
if(chk(P[i].THETA())){
double X=0;
if(P[i].S.y<P[i].T.y)
X=P[i].S.x;
else X=P[i].T.x;
X=rk(X);
int w=g(X);
if(w!=-1)ok[i]=ok[w];
if(P[i].oc==NOW&&w==-1){
ok[i]=1;
int A=P[i].S.y,B=P[i].T.y;
if(fabs(P[i].S.x)<eps)
swap(A,B);
if(A<B&&fabs(A-B)>eps)return ;
}
// cout<<w<<" "<<rk(P[i].S.x)<<"x"<<rk(P[i].S.y)<<" "<<rk(P[i].T.x)<<"x"<<rk(P[i].T.y)<<" "<<P[i].oc<<" "<<P[i].askid<<" "<<ok[i]<<endl;
}
mod(rk(P[i].S.x),rk(P[i].T.x),i);
}
for(int i=1;i<=n;i++)
if(ok[i]){
ANS[P[i].askid]=1;
// if(P[i].askid==8){
// cout<<theta<<endl;
// exit(0);
// }
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("planb2.in","r",stdin);
//freopen("planb.out","w",stdout);
// cout<<atan2(1,0)<<endl;
// cout<<atan2(0,1)<<endl;
// cout<<atan2(-1,0)<<endl;
// cout<<atan2(0,-1)<<endl;
// cout.flush();
cin>>n;
for(int i=1;i<=n;i++){
node A,B;
cin>>A.x>>A.y>>B.x>>B.y;
T[i]=line(A,B,i,0);
T[i].chk();
}
cin>>q;
for(int i=1;i<=q;i++){
node A;
cin>>A.x>>A.y;
++n;
T[n]=line(A,A,n,i);
}
//cout<<atan2l(0,-1)<<endl;
for(int i=1;i<=n;i++){
NOW=i;
memset(ok,0,sizeof(ok));
// cout<<T[i].S.THETA()<<" ";
calc(pi/2-T[i].S.THETA());
memset(ok,0,sizeof(ok));
calc(pi/2-T[i].T.THETA());
}
for(int i=1;i<=q;i++)
if(ANS[i])
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
cout.flush();
return 0;
}
/*