蒟蒻求助朴素题
查看原帖
蒟蒻求助朴素题
455490
Sharpsmile楼主2023/12/26 15:24

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;
}
/*
2023/12/26 15:24
加载中...