萌新求助闵可夫斯基和
查看原帖
萌新求助闵可夫斯基和
483966
一粒夸克楼主2021/12/25 22:08
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long  x,y;
	node(long long _x=0,long long _y=0){x=_x;y=_y;}
	inline long long len(){return x*x+y*y;}
	inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
	inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
	inline long long operator *(const node &b)const{return x*b.y-y*b.x;}
	inline bool operator ==(const node &b)const{
		return x==b.x&&y==b.y;
	}
}stk[100005];
inline bool cmp1(node x,node y){
	if(x.y==y.y)return x.x<y.x;
	return x.y<y.y;
}
inline bool cmp2(node x,node y){
	if(!(x*y))return x.len()<y.len();
	return x*y>0;
}
int top;
struct Tubao{
	vector<node> vec;
	inline auto begin(){return vec.begin();}
	inline auto end(){return vec.end();}
	inline auto &back(){return vec.back();}
	inline int size(){return vec.size();}
	inline node& operator [](int t){return vec[t];}
	Tubao(vector<node> A){
		sort(A.begin(),A.end(),cmp1);top=0;
		node T=A[0];for(auto &x:A)x=x-T;
		sort(A.begin()+1,A.end(),cmp2);
		for(auto x:A){
			while(top>2&&(x-stk[top])*(stk[top]-stk[top-1]))top--;
			stk[++top]=x;
		}vec.resize(top);
		for(int i=1;i<=top;i++)vec[i-1]=stk[i]+T;//vec[top]=A[1]+T;
		vec.erase(unique(vec.begin(),vec.end()),vec.end());
	}
	inline Tubao operator +(Tubao B){
		vector<node> res,le,ri;res.push_back(vec[0]+B[0]);
		for(int i=1;i<vec.size();i++)le.push_back(vec[i]-vec[i-1]);
		le.push_back(vec[0]-vec.back());
		for(int i=1;i<B.size();i++)ri.push_back(B[i]-B[i-1]);
		ri.push_back(B[0]-B.back());
		auto it1=le.begin(),it2=ri.begin();
		while(it1!=le.end()&&it2!=ri.end())res.push_back(cmp2(*it1,*it2)?*it1++:*it2++);
		while(it1!=le.end())res.push_back(*it1++);
		while(it2!=ri.end())res.push_back(*it2++);
		for(int i=1;i<res.size();i++)res[i]=res[i]+res[i-1];
		return Tubao(res);
	}
	inline bool check(node A){
		if(A*vec[0]>0||A*vec.back()>0)return 0;
		int pos=lower_bound(vec.begin(),vec.end(),A,cmp2)-vec.begin();
		return (A-vec[pos])*(vec[(pos+1)%vec.size()]-vec[pos])<=0;
	}
};
int n,m,q;
int main(){
	scanf("%d%d%d",&n,&m,&q);
	vector<node> le,ri;
	for(int i=1;i<=n;i++){
		long long x,y;scanf("%lld%lld",&x,&y);
		le.push_back(node(x,y));
	}
	for(int i=1;i<=m;i++){
		long long x,y;scanf("%lld%lld",&x,&y);
		ri.push_back(node(-x,-y));
	}
	Tubao ans=Tubao(le)+Tubao(ri);
	node T=ans[0];
//	for(auto x:ans)printf("%lld %lld\n",x.x,x.y);
	for(auto &x:ans)x=x-T;
	while(q--){
		long long x,y;scanf("%lld%lld",&x,&y);
		printf("%d\n",ans.check(node(x,y)-T));
	}

	return 0;
}



2021/12/25 22:08
加载中...