三天了,霸屏两页了,还是只对前两个点,求调
查看原帖
三天了,霸屏两页了,还是只对前两个点,求调
275989
LingHusama楼主2023/8/11 22:41
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x;
	long long y;
	int id;
}dota[500005],dotb[500005],sa[500005],sb[500005],sc[500005],tsc[500005];
double eps=1e-10;
long long minax,minbx,minay,minby,mincx,mincy;
long long check(node a1,node a2,node b1,node b2){
	node A=(node){a2.x-a1.x,a2.y-a1.y};
	node B=(node){b2.x-b1.x,b2.y-b1.y};
	long long ret=A.x*B.y-A.y*B.x;
	if(abs(ret)==0){
		ret=0;
	}
	return ret;
}
double dis(node x,node y){
	return sqrt(1.0*(x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
bool cmp(node p1,node p2)//排序函数,这个函数别写错了,要不然功亏一篑 
{
    long long tmp=check(dota[1],p1,dota[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(dota[1],p1)<dis(dota[1],p2)) 
		return 1;
    return 0;
}
bool cmp2(node p1,node p2)//排序函数,这个函数别写错了,要不然功亏一篑 
{
    long long tmp=check(dotb[1],p1,dotb[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(dotb[1],p1)<dis(dotb[1],p2)) 
		return 1;
    return 0;
}
bool cmpc(node p1,node p2)//排序函数,这个函数别写错了,要不然功亏一篑 
{
    long long tmp=check(sc[1],p1,sc[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(sc[1],p1)<dis(sc[1],p2)) 
		return 1;
    return 0;
}
int topa=0;
int topb=0; 
bool pan(node x,node y,node k){//栈头点/栈次点/将要加入的点 ,返回是否要弹出栈头 
	if(check(y,x,x,k)>0){
		return 0;
	}
	else{
		return 1;//在一条线上的暂时视为删除 
	}
}node bs;
bool cmpfd(const node&A,const node&B) {return check(bs,A,bs,B)>0||(fabs(check(bs,A,bs,B))<=eps&&dis(bs,A)<dis(bs,B));}
int tot=0;

void mic(){//闵可夫斯基和 
	int ka=1;
	int kb=1;
	while(ka<topa||kb<topb){
		
	 	node newnode=(node){sa[ka].x+sb[kb].x,sa[ka].y+sb[kb].y};
//	 	printf("ka:%d, kb: %d, newnodex: %lf, newnodey: %lf\n",ka,kb,newnode.x,newnode.y); 
	 	tot++;
	 	sc[tot]=newnode;
	 	long long tmp=check(sa[ka],sa[ka+1],sb[kb],sb[kb+1]);//比较两个邻接点的序
//	 	printf("saka:%lf %lf ",sa[ka].x,sa[ka].y);
//	 	printf("saka+1:%lf %lf ",sa[ka+1].x,sa[ka+1].y);
//	 	printf("sakb:%lf %lf ",sb[kb].x,sb[kb].y);
//	 	printf("sakb+1:%lf %lf ",sb[kb+1].x,sb[kb+1].y);
//	 	printf("ck:%lf\n",tmp);
	 	if(ka==topa){
	 		kb++;
	 		continue;
		}
		if(kb==topb){
			ka++;
			continue;
		} 
		if(tmp==0){
			ka++;kb++;
		} 
		else if(tmp>0){//b在a的左手,说明a更小 
			ka++; 
		}
		else{
			kb++;
		}
	}
	sc[0]=sc[tot];
	sc[tot+1]=sc[1];
	//此时至少有一个点饱和了 
}
bool finda(double x,double y){/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	node key=(node){x,y};
	if(check(bs,key,bs,sc[1])>0){//在最低端点的下方,不行
		return 0;
	}
	if(check(bs,sc[tot],bs,key)>0){//在最高点的左侧,也不行  (有问题) !!!!!!!!!!!!!!!!!!!!!!!!!!
		return 0;
	} 
	
	long long ps=lower_bound(sc+1,sc+tot+1,key,cmpfd)-sc-1;
	if(check(sc[ps],key,sc[ps],sc[ps+1])<=0){
		return 1;
	}
	else{
		return 0;
	}
}
int main(){
	ios::sync_with_stdio(false);
	int n,m,q;
	cin >> n >> m >> q;
	minax=minay=minbx=minby=mincx=mincy=1e10;
	int posa,posb,posc;
	for(int i=1;i<=n;i++){
		cin >> dota[i].x >> dota[i].y;
		if(minay>dota[i].y){
			minax=dota[i].x;
			minay=dota[i].y;
			posa=i;
		}
		else if(minay==dota[i].y&&minax>dota[i].x){
			minax=dota[i].x;
			posa=i;
		}
		dota[i].id=i;
	}
	swap(dota[1],dota[posa]);
	
	if(n==1){
		topa=1;
		sa[1]=dota[1];
	}
	else if(n==2){
		topa=2;
		sa[1]=dota[1];
		sa[2]=dota[2];
	}
	else{
		sort(dota+1,dota+1+n,cmp);
		topa=2;
		sa[1]=dota[1];
		sa[2]=dota[2];
		for(int i=3;i<=n;i++){
			while(topa>=2&&pan(sa[topa],sa[topa-1],dota[i])==1){
				topa--;
			}
			topa++;
			sa[topa]=dota[i];
		}
	}
	//开始着手b !!!!!!!!!!!!!!!!!!!!!
	for(int i=1;i<=m;i++){
		cin >> dotb[i].x >> dotb[i].y;
		dotb[i].x=0-dotb[i].x;
		dotb[i].y=0-dotb[i].y;//取反,后面才能闵可夫斯基和 
		if(minby>dotb[i].y){
			minbx=dotb[i].x;
			minby=dotb[i].y;
			posb=i;
		}
		else if(minby==dotb[i].y&&minbx>dotb[i].x){
			minbx=dotb[i].x;
			posb=i;
		}
		dotb[i].id=i;
	}
	
	swap(dotb[1],dotb[posb]);
	if(m==1){
		topb=1;
		sb[1]=dotb[1];
	}
	else if(m==2){
		
		topb=2;
		sb[1]=dotb[1];
		sb[2]=dotb[2];
	}
	else{
		sort(dotb+1,dotb+1+m,cmp2);
		
		topb=2;
		sb[1]=dotb[1];
		sb[2]=dotb[2];
		for(int i=3;i<=m;i++){
			while(topb>=2&&pan(sb[topb],sb[topb-1],dotb[i])==1){
				topb--;
			}
			topb++;
			sb[topb]=dotb[i];
		}
	} 
	//先把两者的凸包搞定了
	topa++;
	sa[topa]=sa[1];
	topb++;
	sb[topb]=sb[1];
	
	mic(); //进行合并
	for(int i=1;i<=tot;i++){
		if(mincy>sc[i].y){
			mincx=sc[i].x;
			mincy=sc[i].y;
			posc=i;
		}
		else if(mincy==sc[i].y&&mincx>sc[i].x){
			mincx=sc[i].x;
			posc=i;
		}
		sc[i].id=i;
	}
	swap(sc[1],sc[posc]);
	sort(sc+2,sc+1+tot,cmpc);
	int topc=2;
	tsc[1]=sc[1];
	tsc[2]=sc[2];
	for(int i=3;i<=tot;i++){
			while(topc>=2&&pan(tsc[topc],tsc[topc-1],sc[i])==1){
				topc--;
			}
		topc++;
		tsc[topc]=sc[i];
	}
	tot=topc;
	for(int i=1;i<=tot;i++){
		sc[i]=tsc[i];
//		cout<<"ans:"<<sc[i].x<<" "<<sc[i].y<<endl;
	}
	bs=sc[1];
	while(q--){
		long long a,b;
		cin >> a >> b;//现在关键在于如何判断这个点是否在c图内部了 
		cout<<finda(a,b)<<endl;
	} 

}
2023/8/11 22:41
加载中...