求助闵可夫斯基和
查看原帖
求助闵可夫斯基和
171544
cp152楼主2022/3/14 19:44
#include<bits/stdc++.h>
using namespace std;
struct vec{
	int x,y;
	vec operator + (vec a)	const
	{
		vec ans;
		ans.x=x+a.x;
		ans.y=y+a.y;
		return ans;
	}
	vec operator - (vec a)	const
	{
		vec ans;
		ans.x=x-a.x;
		ans.y=y-a.y;
		return ans;
	}
}a[100005],b[100005],fa[100005],fb[100005],c[200005];
struct A{
	int x,y,id;
}que[100005];
bool cmp(vec a,vec b)
{
	return a.x<b.x;
}
bool cm(A a,A b)
{
	if(a.x!=b.x)	return a.x<b.x;
	return a.y<b.y;
}
int cross(vec a,vec b)
{
	return a.x*b.y-a.y*b.x;
}
int n,m,q;
int za[100005],ta;
bool va[100005];
int zb[100005],tb;
bool vb[100005];
bool ans[100005];
int mi,ma;
int tmp;
int main() 
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&b[i].x,&b[i].y);
		b[i].x=-b[i].x;
		b[i].y=-b[i].y;
	}
		
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+m+1,cmp);
	
	za[++ta]=1;
	for(int i=2;i<=n;i++)
	{
		while(ta>1&&cross(a[za[ta]]-a[za[ta-1]],a[i]-a[za[ta-1]])<=0)	va[za[ta--]]=0;
		za[++ta]=i;
		va[i]=1;
	}
	tmp=ta;
	for(int i=n-1;i>=1;i--)
	{
		if(va[i])	continue;
		while(ta>tmp&&cross(a[za[ta]]-a[za[ta-1]],a[i]-a[za[ta-1]])<=0)	va[za[ta--]]=0;
		za[++ta]=i;
		va[i]=1;
	}
	for(int i=1;i<=ta;i++)	fa[i]=a[za[i]];
	
	zb[++tb]=1;
	for(int i=2;i<=m;i++)
	{
		while(tb>1&&cross(b[zb[tb]]-b[zb[tb-1]],b[i]-b[zb[tb-1]])<=0)	vb[zb[tb--]]=0;
		zb[++tb]=i;
		vb[i]=1;
	}
	tmp=tb;
	for(int i=m-1;i>=1;i--)
	{
		if(vb[i])	continue;
		while(tb>tmp&&cross(b[zb[tb]]-b[zb[tb-1]],b[i]-b[zb[tb-1]])<=0)	vb[zb[tb--]]=0;
		zb[++tb]=i;
		vb[i]=1;
	}
	for(int i=1;i<=tb;i++)	fb[i]=b[zb[i]];
	////////以上为凸包
    
  //////////////////
	c[1]=fa[1]+fb[1];
	mi=c[1].x,ma=a[n].x+b[m].x;
	for(int i=1,j=1;i<ta||j<tb;)
	{
		if((cross(fa[i+1]-fa[i],fb[j+1]-fb[j])<0||i>=ta)&&(j<tb))	++j;
		else														++i;
		c[i+j-1]=fa[i]+fb[j];
	}
	/////////////////闵可夫斯基和
    
    
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&que[i].x,&que[i].y);
		que[i].id=i;
	}
	sort(que+1,que+q+1,cm);
	int nd=1,nu=ta+tb-1;
	for(int i=1;i<=q;i++)
	{
		if(que[i].x<mi)	continue;
		if(que[i].x>ma)	break;
		while(c[nd+1].x<que[i].x||c[nd+1].x==c[nd].x)
		{
			nd++;
		}
		while(c[nu-1].x<que[i].x||c[nu-1].x==c[nu].x)
		{
			nu--;
		}
		if(ceil(c[nd].y+(c[nd+1].y-c[nd].y)*(que[i].x-c[nd].x)/(c[nd+1].x-c[nd].x))<=que[i].y&&c[nu].y+(c[nu-1].y-c[nu].y)*(que[i].x-c[nu].x)/(c[nu-1].x-c[nu].x)>=que[i].y)	ans[que[i].id]=1;
	}
    ////////////离线处理询问
    
    
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

2022/3/14 19:44
加载中...