题意
给你两个点集。
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;
}