求助嘤嘤嘤
查看原帖
求助嘤嘤嘤
227836
road楼主2022/11/3 23:00
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q,tot;
struct node{
	int x,y;
	void read(){ scanf("%d%d",&x,&y); }
	void write(){ printf("\n%d %d\n",x,y); }
	void change(){ x=-x,y=-y; }
	int len(){ return x*x+y*y; }
}a[N],b[N],c[N],tmp;
node operator + (node a,node b){ return (node){ a.x+b.x,a.y+b.y }; }
node operator - (node a,node b){ return (node){ a.x-b.x,a.y-b.y }; }
int operator * (node a,node b){ return a.x*b.y-a.y*b.x; }

bool cmp(node a,node b){ return a.y==b.y ? a.x<b.x : a.y<b.y; }
bool check(node a,node b){
	int flag=a*b;
	return flag ? flag>0 : a.len()<b.len();
}

int convex(node a[],int n){
	sort(a+1,a+n+1,cmp);
	for(int i=2;i<=n;i++)a[i]=a[i]-a[1];
	sort(a+2,a+n+1,check);
	for(int i=2;i<=n;i++)a[i]=a[i]+a[1];
	tot=0;
	for(int i=1;i<=n;i++){
		while(tot>1 && check(a[i]-a[tot-1],a[tot]-a[tot-1]))tot--;
		a[++tot]=a[i];
	}
	a[tot+1]=a[1];
	return tot;
}

void minkowski(){
	tot=1; c[tot]=a[1]+b[1];
	for(int i=1;i<=n;i++)a[i]=a[i+1]-a[i];
	for(int i=1;i<=m;i++)b[i]=b[i+1]-b[i];
	int l=1,r=1;
	while(l<=n && r<=m){
		if(check(a[l],b[r])) c[++tot]=c[tot-1]+a[l],l++;
		else c[++tot]=c[tot-1]+b[r],r++;
	}
	while(l<=n) c[++tot]=c[tot-1]+a[l],l++;
	while(r<=m) c[++tot]=c[tot-1]+b[r],r++;
	tot--;
	tot=convex(c,tot);
	for(int i=2;i<=tot;i++)c[i]=c[i]-c[1];
}

bool query(node x){
	x=x-c[1];
	if(x*c[2]>0 || x*c[tot]<0)return 0;
	if(x*c[2]==0 || x*c[tot]==0){
		if(x.len()>c[2].len() && x.len()>c[tot].len())return 0;
		else return 1;
	}
    int l=2,r=tot,pos=l;
    while(l<=r){
        int mid=l+r>>1;
        if(c[mid]*x>=0)pos=mid,l=mid+1;
        else r=mid-1;
    }
    return (x-c[pos])*(c[pos%tot+1]-c[pos])<=0;
}

signed main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)a[i].read();
	for(int i=1;i<=m;i++)b[i].read(),b[i].change();
	n=convex(a,n); m=convex(b,m);
	minkowski();
	for(int i=1;i<=q;i++){
		tmp.read();
		cout<<query(tmp)<<endl;
	}
	return 0;
}

听取WA声一片了呜呜呜

2022/11/3 23:00
加载中...