传送门

写出式子,若存在 $a \in A$,$b \in B$,使得 $b+v=a$,那么此方案会产生冲突

即存在 $a \in A$,$b \in B$,使得 $v=a+(-b)$,设 $C=A+(-B)$ 那么有 $v \in C$,$+$ 表示闵可夫斯基和,$-$ 表示坐标符号取反

所有直接求出 $A$ 和 $-B$ 的闵可夫斯基和的凸包,然后查询 $v$ 是否在凸包内即可

注意直接求闵可夫斯基和的凸包可能会有一些平行的向量,为了方便查询,重新做一遍凸包即可

我的做法会把凸包坐标变化,所以查询的向量也要跟着变化

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
typedef double db;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=2e5+;
struct poi {
ll x,y;
poi (ll a=,ll b=) { x=a,y=b; }
inline poi operator + (const poi &tmp) const { return poi(x+tmp.x,y+tmp.y); }
inline poi operator - (const poi &tmp) const { return poi(x-tmp.x,y-tmp.y); }
inline bool operator < (const poi &tmp) const { return x!=tmp.x ? x<tmp.x : y<tmp.y; }
}A[N],B[N],C[N],st[N],sum;
inline ll Cross(poi A,poi B) { return A.x*B.y-A.y*B.x; }
inline db Dot(poi A,poi B) { return A.x*B.x+A.y*B.y; }
inline db Len(poi A) { return sqrt(Dot(A,A)); }
inline bool cmp(const poi &A,const poi &B) { return Cross(A,B)>||(Cross(A,B)==&&Len(A)<Len(B)); }
void Tubao(poi *P,int &tot)
{
sort(P+,P+tot+); sum=sum+P[];/*如果此时求的是C的凸包P[1]=(0,0)没有贡献*/ for(int i=tot;i>=;i--) P[i]=P[i]-P[];
sort(P+,P+tot+,cmp); int Top=;
for(int i=;i<=tot;st[++Top]=P[i],i++)
while(Top> && Cross(P[i]-st[Top-],st[Top]-st[Top-])>= ) Top--;
tot=Top; for(int i=;i<=tot;i++) P[i]=st[i];
}
int check(poi *P,int tot,poi A)
{
A=A-sum;
if(Cross(A,P[])>||Cross(P[tot],A)>) return ;
int pos=lower_bound(P+,P+tot+,A,cmp)-P-; if(pos==tot) return ;
return Cross(A-P[pos],P[pos+]-P[pos])<=;
}
int n,m,T,Q;
int main()
{
n=read(),m=read(),Q=read();
for(int i=;i<=n;i++) A[i].x=read(),A[i].y=read();
for(int i=;i<=m;i++) B[i].x=-read(),B[i].y=-read();
Tubao(A,n); Tubao(B,m);
int la=,lb=; C[++T]=A[]+B[];
while(la<=n||lb<=m)
{
poi p1=A[la%n+]+B[(lb-)%m+],p2=A[(la-)%n+]+B[lb%m+];
if(Cross(p1-C[T],p2-C[T])>=) la++,C[++T]=p1;
else lb++,C[++T]=p2;
}
Tubao(C,T);
for(int i=;i<=Q;i++)
{
int x=read(),y=read();
printf("%d\n",check(C,T,poi(x,y)));
}
return ;
}

最新文章

  1. windows  远程桌面命令 mstsc
  2. CSS/块级元素与内联元素的深入理解
  3. C++学习笔记(四):枚举
  4. 【转】jQuery列表拖动排列-jquery list dragsort插件参数和使用方法
  5. Eclipse formater(google Java 编码规范)
  6. 一些实用的CSS Media Query代码片段,个人采集
  7. java与javac命令笔记
  8. python基本数据类型——dict
  9. ngRx 官方示例分析 - 3. reducers
  10. 设计模式——职责链模式(C++实现)
  11. ●BZOJ 4710 [Jsoi2011]分特产
  12. ES6(数值)
  13. Redis持久化方式的选择
  14. STL--sort源码分析
  15. MongoDB 备份与还原 mongodump、mongorestore
  16. 【BZOJ4919】[Lydsy六月月赛]大根堆
  17. Java进程和线程
  18. python kafka client--confluent-kafka-python
  19. 线程系列06,通过CLR代码查看线程池及其线程
  20. Additive属性动画

热门文章

  1. JPA学习(三、JPA_API)
  2. Python字典实现
  3. promql 常用函数介绍
  4. DVWA--XSS(DOM)
  5. 20182335实验一《Linux基础与Java开发环境》
  6. zabbix 监控安装部署
  7. Flask基础以及Response三剑客
  8. JavaScript对象---递归遍历对象
  9. 【mysql】时间类型-如何根据不同的应用场景,选择合适的时间类型?
  10. msyql 计划任务 备份数据库