题意

给你两个点集。

q次询问 , 每次把其中一个点集往一个方向移动 , 问两个点集的凸包还有没有交。

Sol

闵可夫斯基和板子题。

把问题做如下转换:

我们本来两个凸包相交是相当于是对于移动向量 \(c\) 来说 , 存在分别在两个点集中的向量 \(a,b\) 有 \(b+c=a\)

也就是 \(c=a-b, c=a+(-b)\)

我们先求出第一个点集的凸包和第二个点集的按原点对称后的凸包。

现在要做的就是求出一个凸多边形 \(C\) 满足两个点集中的任意一对向量的和在该凸多边形内部。

之后我们就只需要判断点是否在凸包内。

这个就可以用闵可夫斯基和来解决。

求解方法:

首先求出这两个向量集合构成的凸包。

然后以按照最小向量和为起点对所有凸包上的边极角排序,一个个顺次连起来就做完了。

做完后由于可能出现共线情况就再求一次凸包。

关于判断点是否在凸包内:

以凸包左下角的点为极点 , 二分找到第一个极角小于给定向量的边(没有则不在凸包内) , 判断下一条边的向量和给定向量到这个向量差向量的方向关系 , 如果在左边则给定向量不在凸包内。

#include<bits/stdc++.h>

using namespace std;

#define Set(a,b) memset(a,b,sizeof(a))

template<class T>inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);

	if(t) x=-x;return;

}typedef long long ll;

typedef double R;

const int N=1e5+10;

const R PI=acos(-1),eps=1e-10;

int n,m,q;

struct point{

	R x,y;

	point(R _x=0.0,R _y=0.0){x=_x,y=_y;}

	inline bool operator <(const point b)const{return x<b.x||(x==b.x&&y<b.y);}

	inline R operator *(const point b)const{return x*b.y-b.x*y;}

	inline point operator *(const R d){return point(x*d,y*d);}

	inline point operator /(const R d){return point(x/d,y/d);}

	inline point operator +(const point b){return point(x+b.x,y+b.y);}

	inline point operator -(const point b){return point(x-b.x,y-b.y);}

	inline R len(){return sqrt(x*x+y*y);}

}P1[N],P2[N];

inline int fcmp(R x){if(x>eps) return 1;if(x<-eps) return -1;return 0;}

inline bool cmp(point A,point B){return A*B>0||(A*B==0&&A.len()<B.len());}

inline void Convex_Hull(point*P,int&n){

	sort(P+1,P+1+n);point Base=P[1];

	for(int i=n;i;--i) P[i]=P[i]-Base;

	sort(P+2,P+1+n,cmp);int r=1;

	for(int i=2;i<=n;++i) {while(r>1&&(P[i]-P[r])*(P[r]-P[r-1])>=0) --r;P[++r]=P[i];}

	n=r;for(int i=1;i<=n;++i) P[i]=P[i]+Base;

	return;

}

struct line{

	point A,B;R ang;

	line(point _A=point(),point _B=point()){A=_A,B=_B-_A,ang=atan2(B.y,B.x);}

	inline bool operator <(const line b)const{return ang<b.ang;}

};

inline void Minkowski_Sum(point*A,point*B,int n,int m,point*C,int&node){

	A[n+1]=A[1],B[m+1]=B[1];node=0;

	static point L1[N],L2[N];int l1=0,l2=0;

	for(int i=1;i<=n;++i) L1[i]=A[i+1]-A[i];

	for(int i=1;i<=m;++i) L2[i]=B[i+1]-B[i];

	point Base=A[1]+B[1];C[node=1]=Base;

	l1=l2=1;

	while(l1<=n&&l2<=m) ++node,C[node]=C[node-1]+(L1[l1]*L2[l2]>=0? L1[l1++]:L2[l2++]);

	while(l1<=n) ++node,C[node]=C[node-1]+L1[l1++];

	while(l2<=m) ++node,C[node]=C[node-1]+L2[l2++];

	Convex_Hull(C,node);return;

}

point Ans[N<<1];int node=0;

inline bool Judge(point A){// 点是否在凸包内

	if(A*Ans[2]>0||A*Ans[node]<0) return 0;

	int p=lower_bound(Ans+1,Ans+1+node,A,cmp)-Ans-1;

	return (A-Ans[p])*(Ans[p%node+1]-Ans[p])<=0;

}

int main()

{

	init(n),init(m),init(q);

	int x,y;

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

		init(x),init(y);

		P1[i]=point(x,y);

	}

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

		init(x),init(y);

		x=-x,y=-y;

		P2[i]=point(x,y);

	}

	Convex_Hull(P1,n);

	Convex_Hull(P2,m);

	Minkowski_Sum(P1,P2,n,m,Ans,node);

	point base=Ans[1];

	for(int i=1;i<=node;++i) Ans[i]=Ans[i]-base;

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

		init(x),init(y);

		point B=point(x,y)-base;

		if(Judge(B)) puts("1");

		else         puts("0");

	}

	return 0;

}

巴特西

【LuoguP4557】[JSOI2018]战争

题意

Sol

最新文章

热门文章