时间戳

首页 > 技术文章 > 弱菜的各种模板

弱菜的各种模板

cx233666 2018-10-02 16:53 原文

高斯-约当消元

这里以JSOI2008球形空间产生器做例题）

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define db double
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
db a[15][15];
int p[15],o[15];
const db eps=1e-3;
int main()
{
	int n=in()+1;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<n;++j)
			scanf("%lf",a[i]+j),a[i][n+1]+=a[i][j]*a[i][j],a[i][j]*=2;
		a[i][n]=1;
	}	
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)if(!o[j]&&fabs(a[j][i])>eps){p[i]=j;break;}
		double t=a[p[i]][i];o[p[i]]=1;
		for(int j=1;j<=n+1;++j)a[p[i]][j]/=t;
		for(int k=1;k<=n;++k)
		{
			if(p[i]==k)continue;
			t=a[k][i];
			for(int j=1;j<=n+1;++j)a[k][j]-=a[p[i]][j]*t;
		}
	}
	for(int i=1;i<n;++i)printf("%.3lf ",a[p[i]][n+1]);puts("");
	return 0;
}

今天考试判断这一行是否为零时用了eps，然后挂了，所以一定不要管它有没有值，直接减，只要判不是同一行就行了QAQ

NTT

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
const int YL=998244353,g=3,N=3e6+5;
int a[N],b[N],rev[N];
void get_rev(int len,int qwq){for(int i=1;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<qwq-1);}
inline int ksm(int a,int k){int r=1;while(k){if(k&1)r=1ll*r*a%YL;a=1ll*a*a%YL,k>>=1;}return r;}
inline int MO(const int &a){return a>=YL?a-YL:a;}
void ntt(int *a,int len,int opt)
{
	for(int i=0;i<len;++i)if(i<rev[i])std::swap(a[i],a[rev[i]]);
	for(int st=2,m=1;st<=len;st<<=1,m<<=1)
	{
		int wn=ksm(g,opt==1?(YL-1)/st:YL-1-(YL-1)/st);
		for(int *p=a,x,y;p!=a+len;p+=st)
			for(int k=0,wnk=1;k<m;++k,wnk=1ll*wnk*wn%YL)
				x=p[k],y=1ll*p[k+m]*wnk%YL,p[k]=MO(x+y),p[k+m]=MO(x-y+YL);
	}
	if(opt==1)return;int inv=ksm(len,YL-2);
	for(int i=0;i<len;++i)a[i]=1ll*a[i]*inv%YL;
}
int main()
{
	int n=in()+1,m=in()+1;
	for(int i=0;i<n;++i)a[i]=in();
	for(int i=0;i<m;++i)b[i]=in();
	int len=1,qwq=0;
	while(len<=n+m-1)++qwq,len<<=1;
	get_rev(len,qwq);
	ntt(a,len,1),ntt(b,len,1);
	for(int i=0;i<len;++i)a[i]=1ll*a[i]*b[i]%YL;
	ntt(a,len,-1);
	for(int i=0;i<n+m-1;++i)printf("%d ",a[i]);puts("");
	return 0;
}

splay

CF809D

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=3e5+5;
#define lc ch[x][0]
#define rc ch[x][1]
int ch[N][2],siz[N],val[N],lz[N],fa[N],rt,cnt,le[N],ri[N];
#define down(t) if(t)val[t]+=lz[x],lz[t]+=lz[x]
inline void ps(int x){if(x&&lz[x]){down(lc);down(rc);lz[x]=0;}}
inline void pushup(int x){if(x)siz[x]=siz[lc]+siz[rc]+1;}
inline bool pd(int x){return ch[fa[x]][1]==x;}
inline void rotate(int x)
{
	int y=fa[x],z=fa[y],d=pd(x),w=ch[x][d^1];ps(y);ps(x);
	if(z)ch[z][pd(y)]=x;ch[x][d^1]=y,ch[y][d]=w;
	fa[x]=z,fa[y]=x;if(w)fa[w]=y;pushup(y);
}
inline void splay(int x,int aim=0)
{
	for(int y=fa[x];x&&(y^aim);rotate(x),y=fa[x])
		if(fa[y]^aim)pd(x)^pd(y)?rotate(x):rotate(y);
	if(!x)return;pushup(x);if(aim==0)rt=x;
}
inline void insert(int &x,int v,int pa=0)
{
	if(!x){val[x=++cnt]=v,siz[cnt]=1,fa[x]=pa;splay(x);return;}
	if(v==val[x])return;ps(x);insert(ch[x][v>val[x]],v,x);pushup(x);
}
inline void Del(int x)
{
	if(!x)return;splay(x);int u=lc;
	while(u&&ch[u][1])u=ch[u][1];
	if(!u){rt=rc;if(rc)fa[rc]=0;return;}
	splay(u);if(rc)fa[rc]=u;ch[u][1]=rc;pushup(u);
}
inline int pre(int v){int x=rt,pr=0;while(x){ps(x);if(val[x]>=v)x=lc;else pr=x,x=rc;}return pr;}
inline int nxt(int v){int x=rt,pr=0;while(x){ps(x);if(val[x]< v)x=rc;else pr=x,x=lc;}return pr;}
int main()
{
	int n=in();
	for(int i=1;i<=n;++i)le[i]=in(),ri[i]=in();
	insert(rt,le[1]);
	for(int i=2;i<=n;++i)
	{
		int l=le[i],r=ri[i],p=pre(l),q=nxt(r);
		splay(p,0);splay(q,p);
		if(!p&&!q)++lz[rt],++val[rt];
		else
		{
			if(!q){if(ch[p][1])++lz[ch[p][1]],++val[ch[p][1]];}
			else if(ch[q][0])++val[ch[q][0]],++lz[ch[q][0]];Del(q);
		}
		insert(rt,l);int x=rt;while(rc)x=rc;splay(x);
	}
	printf("%d\n",siz[rt]);
	return 0;
}

树剖

洛谷模板题

#include<cstdio>
#include<algorithm>
#define gt getchar()
#define ls l,mid,k<<1
#define rs mid+1,r,k<<1|1
#define ps sum[k]=MO(sum[k<<1]+sum[k<<1|1])
inline int in(){int k;scanf("%d",&k);return k;}
const int N=1e5+5;int YL;
inline int MO(const int &a){return a>=YL?a-YL:a;}
inline void add(int &x,int y){x+=y;if(x>=YL)x-=YL;}
int head[N],to[N<<1],nxt[N<<1],cnt,val[N],son[N],top[N],siz[N],fa[N],dep[N],n,id[N],pos[N],sum[N<<2],lz[N<<2];
inline void link(int u,int v){to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;to[++cnt]=u,nxt[cnt]=head[v],head[v]=cnt;}
void dfs(int u,int pa=0)
{
	siz[u]=1,fa[u]=pa;dep[u]=dep[pa]+1;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=to[i])!=pa)dfs(v,u),son[u]=(siz[son[u]]<siz[v]?v:son[u]),siz[u]+=siz[v];
}
void build(int l,int r,int k)
{
	if(l==r){sum[k]=val[pos[l]];return;}
	int mid=l+r>>1;build(ls),build(rs);ps;
}
void pushdown(int k,int l,int r)
{
	if(!lz[k])return;int le=1ll*l*lz[k]%YL,ri=1ll*r*lz[k]%YL;
	add(lz[k<<1],lz[k]),add(lz[k<<1|1],lz[k]),add(sum[k<<1],le),add(sum[k<<1|1],ri);lz[k]=0;
}
void update(int L,int R,int l,int r,int k,int ad)
{
	if(L<=l&&r<=R){int t=1ll*ad*(r-l+1)%YL;add(sum[k],t);add(lz[k],ad);return;}
	int mid=l+r>>1;pushdown(k,mid-l+1,r-mid);if(L<=mid)update(L,R,ls,ad);if(R> mid)update(L,R,rs,ad);ps;
}
int query(int L,int R,int l,int r,int k)
{
	if(L<=l&&r<=R)return sum[k];int mid=l+r>>1,ans=0;pushdown(k,mid-l+1,r-mid);
	if(L<=mid)add(ans,query(L,R,ls));if(R> mid)add(ans,query(L,R,rs));return ps,ans;
}
#define pd if(dep[top[u]]<dep[top[v]])std::swap(u,v)
void Dfs(int u,int tp)
{
	top[u]=tp,id[u]=++cnt,pos[cnt]=u;if(son[u])Dfs(son[u],tp);
	for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=fa[u]&&v!=son[u])Dfs(v,v);
}
void change(int u,int v,int ad)
{
	while(top[u]!=top[v]){pd;update(id[top[u]],id[u],1,n,1,ad);u=fa[top[u]];}
	if(dep[u]>dep[v])std::swap(u,v);update(id[u],id[v],1,n,1,ad);
}
int ask(int u,int v,int ans=0)
{
	while(top[u]!=top[v]){pd;add(ans,query(id[top[u]],id[u],1,n,1));u=fa[top[u]];}
	if(dep[u]>dep[v])std::swap(u,v);add(ans,query(id[u],id[v],1,n,1));return ans;
}
int main()
{
	n=in();int m=in(),s=in(),op,x,y,z;YL=in();
	for(int i=1;i<=n;++i)val[i]=in();
	for(int i=2;i<=n;++i)link(in(),in());cnt=0;
	dfs(s);Dfs(s,s);build(1,n,1);
	for(int i=1;i<=m&&(op=in(),x=in(),1);++i)
		switch(op)
		{
		case 1:y=in(),z=in()%YL,change(x,y,z);break;
		case 2:y=in(),printf("%d\n",ask(x,y));break;
		case 3:z=in()%YL,update(id[x],id[x]+siz[x]-1,1,n,1,z);break;
		case 4:printf("%d\n",query(id[x],id[x]+siz[x]-1,1,n,1));break;
		}
	return 0;
}

AC自动机(trie图版）

这里以SDOI2017硬币游戏为例

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
const int N=305,M=1e5+5;
const double eps=1e-10,P=0.5;
int n,m,cnt,ch[M][2],head[M],to[M],nxt[M];
int pos[N],fa[M],sz[M],tot;
double p[N],G[N][N];
char s[N];
inline void add(int u,int v){to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;}
#define v (ch[u][i])
inline void insert(int p)
{
	scanf("%s",s+1);int u=0,i;
	for(int j=1;j<=m;++j)i=s[j]=='H',sz[!v?v=++tot:v]=sz[u]+1,add(u=v,p);
	pos[p]=u;
}
inline void build()
{
	static int q[M];int h=1,t=0,u=0,i;
	for(int i=0;i<=1;++i)if(v)q[++t]=v;
	while(h<=t)for(u=q[h++],i=0;i<2;++i)v?fa[q[++t]=v]=ch[fa[u]][i]:v=ch[fa[u]][i];
}
#undef v
inline void calc(int x)
{
	for(int u=pos[x];u;u=fa[u])
		for(int i=head[u];i;i=nxt[i])
			G[to[i]][x]+=p[m-sz[u]];
}
int o[N];
inline void Gauss(int n)
{
	for(int i=1;i<=n;++i)
	{
		pos[i]=0;
		for(int j=1;j<=n;++j)if(!o[j]&&G[j][i]){pos[i]=j;break;}
		o[pos[i]]=1;double t=G[pos[i]][i];
		for(int j=1;j<=n+1;++j)G[pos[i]][j]/=t;
		for(int k=1;k<=n;++k)
			if(pos[i]!=k)
			{
				t=G[k][i];
				for(int j=1;j<=n+1;++j)G[k][j]-=G[pos[i]][j]*t;
			}
	}
}
int main()
{
	n=in(),m=in();p[0]=1;for(int i=1;i<=m;++i)p[i]=p[i-1]*P;
	for(int i=1;i<=n;++i)insert(i);build();
	for(int i=1;i<=n;++i)calc(i);
	for(int i=1;i<=n;++i)G[i][n+1]=-p[m],G[n+1][i]=1,G[n+1][n+2]=1;
	Gauss(n+1);
	for(int i=1;i<=n;++i)printf("%.10lf\n",G[pos[i]][n+2]);
	return 0;
}

任意模数NTT

好吧其实是MTT，拆系数FFT。
模板题

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}

const int N=3e5+5;
const long double PI=acos(-1);
int a[N],b[N],YL,c[N];
inline int MO(const int &a){return a>=YL?a-YL:a;}

int rev[N];
inline void get_rev(int len,int qwq){for(int i=0;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<qwq-1);}
struct E
{
	double x,y;
	E(){}
	E(double a,double b):x(a),y(b){}
	E operator=(const int &a){x=a,y=0;return *this;}
	E conj(){return E(x,-y);}
}omg[N];
E operator+(const E &a,const E &b){return E(a.x+b.x,a.y+b.y);}
E operator-(const E &a,const E &b){return E(a.x-b.x,a.y-b.y);}
E operator*(const E &a,const E &b){return E(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

inline void get_omg(int len){for(int i=0;i<len;++i)omg[i]=E(cos(PI*i/len),sin(PI*i/len));}
inline void fft(E *a,int len)
{
	for(int i=0;i<len;++i)if(i<rev[i])std::swap(a[i],a[rev[i]]);
	for(int st=2,m=1;st<=len;st<<=1,m<<=1)
		for(E *p=a,x,y;p!=a+len;p+=st)
			for(int k=0;k<m;++k)
				x=p[k],y=omg[len/m*k]*p[k+m],p[k]=x+y,p[k+m]=x-y;
}

inline void mul(int *A,int *B,int *C,int len)
{
	for(int i=0;i<len;++i)A[i]=MO(A[i]+YL),B[i]=MO(B[i]+YL);
	static E a[N],b[N],dfta[N],dftb[N],dftc[N],dftd[N];
	for(int i=0;i<len;++i)a[i]=E(A[i]&32767,A[i]>>15);
	for(int i=0;i<len;++i)b[i]=E(B[i]&32767,B[i]>>15);
	fft(a,len),fft(b,len);
	for(int i=0;i<len;++i)
	{
		int j=(len-i)&(len-1);E da,db,dc,dd;
		da=(a[i]+a[j].conj())*E( 0.5,0);
		db=(a[i]-a[j].conj())*E(0,-0.5);
		dc=(b[i]+b[j].conj())*E( 0.5,0);
		dd=(b[i]-b[j].conj())*E(0,-0.5);
		dfta[j]=da*dc,dftb[j]=da*dd,dftc[j]=db*dc,dftd[j]=db*dd;
	}
	for(int i=0;i<len;++i)a[i]=dfta[i]+dftb[i]*E(0,1);
	for(int i=0;i<len;++i)b[i]=dftc[i]+dftd[i]*E(0,1);
	fft(a,len),fft(b,len);
	for(int i=0;i<len;++i)
	{
		int da=(ll)(a[i].x/len+0.5)%YL;
		int db=(ll)(a[i].y/len+0.5)%YL;
		int dc=(ll)(b[i].x/len+0.5)%YL;
		int dd=(ll)(b[i].y/len+0.5)%YL;
		C[i]=(da+((ll)(db+dc)<<15)+((ll)dd<<30))%YL;
	}
}
int main()
{
	int n=in()+1,m=in()+1;YL=in();
	for(int i=0;i<n;++i)a[i]=in();
	for(int i=0;i<m;++i)b[i]=in();
	int len=1,qwq=0;while(len<=n+m-1)len<<=1,++qwq;
	get_rev(len,qwq);get_omg(len);mul(a,b,c,len);
	for(int i=0;i<n+m-1;++i)printf("%d ",c[i]);puts("");
	return 0;
}

dijkstra

这里用的是\(Kelin\)巨神的模板。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
const int N=1e5+5;
int n,m,s;
namespace Graph
{
	int head[N],to[N<<1],nxt[N<<1],w[N<<1],cnt,dis[N];
	inline void add(int u,int v,int c){to[++cnt]=v,w[cnt]=c,nxt[cnt]=head[u],head[u]=cnt;}
	namespace seg
	{
#define lc x<<1
#define rc x<<1|1
		int mi[N<<2],sgt;
		inline void Set(int n){sgt=1;while(sgt<=n)sgt<<=1;mi[0]=N-1;}
		inline void clear(){for(int i=1;i<=(sgt<<1)+1;++i)mi[i]=0;}
		inline int  cmp(const int &a,const int &b){return dis[a]>dis[b]?b:a;}
		inline void upd(int x,int w){for(int i=x+sgt;dis[mi[i]]>w;i>>=1)mi[i]=x;dis[x]=w;}
		inline void del(int x){mi[x+=sgt]=0;x>>=1;while(x)mi[x]=cmp(mi[lc],mi[rc]),x>>=1;}
	}
	void dij()
	{
		memset(dis,0x3f,n+2<<2);dis[s]=0;
		seg::Set(n);seg::upd(s,0);
		for(int e=1;e<=n;++e)
		{
			int u=seg::mi[1];seg::del(u);
			for(int i=head[u],v;i;i=nxt[i])
				if(dis[v=to[i]]>dis[u]+w[i])
					seg::upd(v,dis[u]+w[i]);
		}
	}
}
int main()
{
	n=in(),m=in(),s=in();
	for(int i=1,u,v,c;i<=m;++i)u=in(),v=in(),c=in(),Graph::add(u,v,c);
	Graph::dij();
	for(int i=1;i<=n;++i)printf("%d ",Graph::dis[i]);puts("");
	return 0;
}

\(EX\_lucas\)

其实是\(gsy\)的板子了，他们好神仙啊。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline ll in()
{
	ll k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
const int N=1e6+5,inf=1e9+7;
struct EX_lucas
{
	int p,pk,fac[N];
	inline void init(){fac[0]=1;for(int i=1;i<=pk;++i)fac[i]=1ll*fac[i-1]*(i%p?i:1)%pk;}
	void ex_gcd(int a,int b,int c,int &x,int &y){b?(ex_gcd(b,a%b,c,y,x),y-=a/b*x):(x=c/a,y=0);}
	inline int inv(int a){int x,y;ex_gcd(a,pk,1,x,y);return (x%pk+pk)%pk;}
	inline int ksm(int a,ll k){int r=1;for(;k;a=1ll*a*a%pk,k>>=1)if(k&1)r=1ll*r*a%pk;return r;}
	inline int mul(ll n){int res=1;while(n)res=1ll*res*ksm(fac[pk],n/pk)%pk*fac[n%pk]%pk,n/=p;return res;}
	inline int C(ll n,ll m,ll YL)
		{
			int a=mul(n),b=mul(m),c=mul(n-m),k=0;
			for(ll i=n;i;i/=p)k+=i/p;
			for(ll i=m;i;i/=p)k-=i/p;
			for(ll i=n-m;i;i/=p)k-=i/p;
			int ans=1ll*a*inv(b)%pk*inv(c)%pk*ksm(p,k)%pk;
			return 1ll*ans*(YL/pk)%YL*inv(YL/pk)%YL;
		}
}a[10];
int YL,x,tot,w[10];
inline int MO(const int &x){return x>=YL?x-YL:x;}
inline int OD(const int &x){return MO(x+YL);}
inline int lucas(ll n,ll m)
{
	if(n<0||m<0||n<m)return 0;int res=0;
	for(int i=1;i<=tot;++i)res=MO(res+a[i].C(n,m,YL));
	return res;
}
int main()
{
	ll n=in(),m=in();YL=x=in();
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
		{
			a[++tot].p=i,a[tot].pk=1;
			while(x%i==0)a[tot].pk*=i,x/=i;
		}
	if(x>1)++tot,a[tot].p=a[tot].pk=x;
	for(int i=1;i<=tot;++i)a[i].init();
	printf("%d\n",lucas(n,m));
	return 0;
}

闵可夫斯基和

神仙玩意，菜鸡一直凸包写挂，调的欲仙欲死。

顺带送一个\(Andrew\)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=2e5+5;
struct Point
{
	ll x,y;
	Point(ll x=0,ll y=0):x(x),y(y){}
	inline Point operator-(const Point &a){return Point(x-a.x,y-a.y);}
	inline Point operator+(const Point &a){return Point(x+a.x,y+a.y);}
	inline ll operator*(const Point &a)const{return x*a.y-y*a.x;}
}A[N],B[N],C[N];
inline ll Len2(const Point &a){return a.x*a.x+a.y*a.y;}
inline bool cmp(const Point &a,const Point &b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
inline bool cmp2(const Point &a,const Point &b){return a*b>0||(a*b==0&&Len2(a)<Len2(b));}

void Convex(Point *a,int &n)
{
#define pd (st[top]-st[top-1])*(a[i]-st[top-1])<=0
	static int top,k;static Point st[N];top=0;std::sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;st[++top]=a[i],++i)while(top>1&&pd)--top;k=top;
	for(int i=n-1;i ;st[++top]=a[i],--i)while(top>k&&pd)--top;--top;
	memcpy(a,st,(top+1)*sizeof(Point));n=top;return;
}
void Minkowski(Point *a,int n,Point *b,int m,Point *c,int &tot)
{
	static Point tmp1[N],tmp2[N];tot=0;
	for(int i=1;i<n;++i)tmp1[i]=a[i+1]-a[i];tmp1[n]=a[1]-a[n];
	for(int i=1;i<m;++i)tmp2[i]=b[i+1]-b[i];tmp2[m]=b[1]-b[m];
	c[++tot]=a[1]+b[1];int i=1,j=1;
	while(i<=n&&j<=m)++tot,c[tot]=c[tot-1]+(tmp1[i]*tmp2[j]>0?tmp1[i++]:tmp2[j++]);
	while(i<=n)++tot,c[tot]=c[tot-1]+tmp1[i++];
	while(j<=m)++tot,c[tot]=c[tot-1]+tmp2[j++];
}
inline int belong(Point *a,int n,Point t)
{
	if(t*a[2]>0||t*a[n]<0)return 0;
	int p=std::lower_bound(a+1,a+n+1,t,cmp2)-a-1;
	return (t-a[p])*(a[p%n+1]-a[p])<=0;
}
int main()
{
	int n=in(),m=in(),q=in(),tot;
	for(int i=1;i<=n;++i)A[i].x= in(),A[i].y= in();Convex(A,n);
	for(int i=1;i<=m;++i)B[i].x=-in(),B[i].y=-in();Convex(B,m);
	Minkowski(A,n,B,m,C,tot);
	Convex(C,tot);Point yd=C[1],tmp;
	for(int i=1;i<=tot;++i)C[i]=C[i]-yd;
	while(q--)
	{
		tmp.x=in(),tmp.y=in();
		printf("%d\n",belong(C,tot,tmp-yd));
	}
	return 0;
}

推荐阅读