传送门
解题思路： 【凸包|bzoj5317: [Jsoi2018]部落战争【凸包/Minkowski sum】】先求凸包。
合法向量相当于凸包A中存在一点经过该向量可到凸包B中。
即A+v? =BA + v → = B，那么 v? =A?Bv → = A ? B
画图发现，这些向量的轮廓就是凸包A绕取反后凸包B坐标平移一圈。
好像这个东西也叫Minkowski sum，即求 {v? =a? +b? ,a? ∈A,b? ∈B}{ v → = a → + b → , a → ∈ A , b → ∈ B }
#include
#define ll long long
using namespace std;
int getint()
{
int i=0,f=1;
char c;
for(c=getchar();
(c!='-')&&(c<'0'||c>'9');
c=getchar());
if(c=='-')c=getchar(),f=-1;
for(;
c>='0'&&c<='9';
c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}const int N=100005;
struct point
{
ll x,y;
point(ll _x=0,ll _y=0):x(_x),y(_y){}
inline friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);
}
inline friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);
}
inline friend ll operator * (const point &a,const point &b){return a.x*b.y-a.y*b.x;
}
inline ll dis(){return x*x+y*y;
}
}p[N],p1[N],p2[N],t[N],v1[N],v2[N];
inline bool cmp(const point &a,const point &b)
{
ll ret=(a-t[1])*(b-t[1]);
if(ret)return ret>0;
else return (a-t[1]).dis()<(b-t[1]).dis();
}
int n,m,tot,Q;
int Graham(point *p,int cnt)
{
for(int i=1;
i<=cnt;
i++)t[i]=p[i];
for(int i=2;
i<=cnt;
i++)if(t[i].x=2&&(t[top]-t[top-1])*(t[i]-t[top-1])<=0)top--;
t[++top]=t[i];
}
for(int i=1;
i<=top;
i++)p[i]=t[i];
return top;
}
void go()
{
for(int i=1;
i<=n;
i++)v1[i]=p1[i%n+1]-p1[i];
for(int i=1;
i<=m;
i++)v2[i]=p2[i%m+1]-p2[i];
int l1=1,l2=1;
p[tot=1]=p1[1]+p2[1];
while(l1<=n&&l2<=m)p[++tot]=p[tot-1]+(v1[l1]*v2[l2]>=0?v1[l1++]:v2[l2++]);
while(l1<=n)p[++tot]=p[tot-1]+v1[l1++];
while(l2<=m)p[++tot]=p[tot-1]+v2[l2++];
tot=Graham(p,tot);
}
int in(point x)
{
if((x-p[1])*(p[2]-p[1])>0||(x-p[1])*(p[tot]-p[1])<0)return 0;
int l=2,r=tot,pos=l;
while(l<=r)
{
int mid=l+r>>1;
if((p[mid]-p[1])*(x-p[1])>=0)pos=mid,l=mid+1;
else r=mid-1;
}
return (p[pos%tot+1]-p[pos])*(x-p[pos])>=0;
}
int main()
{
//freopen("war.in","r",stdin);
//freopen("war.out","w",stdout);
n=getint(),m=getint(),Q=getint();
for(int i=1;
i<=n;
i++)p1[i].x=getint(),p1[i].y=getint();
for(int i=1;
i<=m;
i++)p2[i].x=-getint(),p2[i].y=-getint();
n=Graham(p1,n),m=Graham(p2,m);
go();
while(Q--)
{
point q;
q.x=getint(),q.y=getint();
printf("%d\n",in(q));
}
return 0;
}
? 推荐阅读
- bzoj|Bzoj3817:Sum
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- Bzoj|[BZOJ2187][fraction][类欧几里得算法]
- 类欧几里得算法|[BZOJ2712][[Violet 2]棒球][类欧几里得算法]
- 2017|[BZOJ3817][Sum][类欧几里得算法 数论]
- 数论|BZOJ 3560 DZY Loves Math V 数论
- online|bzoj2286: [Sdoi2011消耗战
- 类欧几里得算法|bzoj3817: Sum【类欧几里得算法】
- bzoj 3817: Sum 类欧几里得算法