[JSOI2018]战争（闵可夫斯基和）

害怕，可怜几何题

果然不会

题目就是说给你两个凸包，每次询问给你一个向量 \(c\) 问你能不能从两个凸包 \(A\) , \(B\) 里分别找到一个点 \(a\) , \(b\) 满足 \(a+c=b\) 。

考虑怎样的向量可以满足。

发现只有让B中的每一个点-A中的每一个点的集合中的向量可以满足。因为把上面的式子化一下就是 \(c=b-a\) 。

凸包B中的点集减去凸包A中的点集。这不是闵可夫斯基和吗？

所以我们把两个凸包的闵可夫斯基和求出，然后每一个询问查看给的向量在不在闵可夫斯基和中即可。

代码极丑，不过我判向量是不是在凸包里是把凸包切成上下两个凸包，然后分类讨论求的。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define int long long

const int N=501000;

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int top1,top2,top;

struct node{

	int x,y;

	node (int xx=0,int yy=0){

		x=xx,y=yy;

	}

}stack1[N],stack2[N],a[N],b[N],ans[N],ans1[N];

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);

}

bool cmp(node a,node b){

	if(a.x==b.x)return a.y<b.y;

	else return a.x<b.x;

}

int chaji(node a,node b){

	return a.x*b.y-a.y*b.x;

}

bool judge(node a,node b,node c){

	return chaji(b-c,a-b)<=0;

}

int n,m;

void tubao1(){

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++){

		while(top1>1&&judge(a[i],stack1[top1],stack1[top1-1]))top1--;

		stack1[++top1]=a[i];

	}

	int k=top1;

	for(int i=n-1;i>=1;i--){

		while(top1>k&&judge(a[i],stack1[top1],stack1[top1-1]))top1--;

		stack1[++top1]=a[i];

	}

	top1--;

}

void tubao2(){

	sort(b+1,b+1+m,cmp);

	for(int i=1;i<=m;i++){

		while(top2>1&&judge(b[i],stack2[top2],stack2[top2-1]))top2--;

		stack2[++top2]=b[i];

	}

	int k=top2;

	for(int i=m-1;i>=1;i--){

		while(top2>k&&judge(b[i],stack2[top2],stack2[top2-1]))top2--;

		stack2[++top2]=b[i];

	}

	top2--;

}

void sum(){

	for(int i=1;i<=top1;i++)a[i]=stack1[i+1]-stack1[i];

	for(int i=1;i<=top2;i++)b[i]=stack2[i+1]-stack2[i];

	ans[top=1]=stack1[1]+stack2[1];

	int now1=1,now2=1;

	while(now1<=top1&&now2<=top2)top++,ans[top]=ans[top-1]+(chaji(a[now1],b[now2])>=0?a[now1++]:b[now2++]);

	while(now1<=top1)top++,ans[top]=ans[top-1]+a[now1++];

	while(now2<=top2)top++,ans[top]=ans[top-1]+b[now2++];

	top--;

}

bool in(node x){

	if(x.x<ans[1].x||x.x>ans[top1].x)return false;

	if(x.x==ans[1].x){

		if(x.y>=ans[1].y&&x.y<=ans1[1].y)return true;

		else return false;

	}

	if(x.x==ans[top1].x){

		if(x.y>=ans[top1].y&&x.y<=ans1[top2].y)return true;

		else return false;

	}

	int A=lower_bound(ans+1,ans+1+top1,x,cmp)-ans;

	int B=lower_bound(ans1+1,ans1+1+top2,x,cmp)-ans1;

	if(chaji(ans1[B]-x,ans1[B-1]-x)>=0&&chaji(ans[A-1]-x,ans[A]-x)>=0)return true;

	else return false;

}

int q;

signed main(){

	n=read();m=read();q=read();

	for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read();

	tubao1();

	for(int i=1;i<=m;i++)b[i].x=-read(),b[i].y=-read();

	tubao2();

	sum();

	for(int i=1;i<=top;i++)

		if(ans[i+1].x<ans[i].x){top1=i;break;}

	for(int i=top1;i<=top+1;i++)

		ans1[i-top1+1]=ans[i];

	top2=top+1-top1+1;

	while(ans[top1-1].x==ans[top1].x)top1--;

	while(ans1[top2-1].x==ans1[top2].x)top2--;

	for(int i=1;i<=top2/2ll;i++)swap(ans1[i],ans1[top2-i+1]);

	while(q--){

		int A=read(),B=read();

		node x=node(A,B);

		if(in(x))printf("1\n");

		else printf("0\n");

	}

	return 0;

}

巴特西

[JSOI2018]战争（闵可夫斯基和）

最新文章

热门文章