题解 P4557 【[JSOI2018]战争】

~~写题解写到一半不小心弄没了体验极差~~ 所以首先我们可以发现这是一道~~可怜~~计算几何题 首先有个重点，题目说的是存在平面上的任何一个点被两个部落包含是不合法情况，而不是$(n+m)$个点中的任何一个被两个部落包含。 考虑一个部落包含的平面上的所有的点，它们其实是一个凸包的形状，这是很显然而且很容易想到的。我们考虑求出这个点集的凸包，把这个凸包三角剖分后，这若干个三角形显然能覆盖整个凸包；而对于一个不在凸包上的点，它与任意其他两个点(不管在不在凸包上)所形成的三角形显然会被这个凸包覆盖。 那么现在问题变成了这样的形式，也就是给出一个向量 $\vec{x}$ ,询问大小为 $m$ 的点集构成的凸包 $B$ 平移向量 $\vec{x}$ 后，与大小为 $n$ 的点集构成的凸包 $A$ 是否有交。 也就是 $$\exists\ b + \vec{x}=a(a\in A,b\in B)$$ 看一眼数据范围，本来我以为是$O(qn)$之类的东西，结果不是......果然做题的时候不能被数据结构误导... 我们考虑转化这个等式 $$\vec{x}\in\{a-b|(a\in A,b\in B)\}$$ 因为$a-b=a+(-b)$，所以把 $B$ 的所有点都取反，求的集合就变成了$\{a+b|(a\in A,b\in B)\}$。如何求这个东西呢？ 先试想点集 $B$ 是一个点的情况，那么结果显然是 $A$ 的平移：  那么再考虑 $B$ 是一条线段的情况，也不难想象应该是这样的：  如果 $B$ 也是一个凸包，相信聪明的你可以知道，结果应该是这样的:  这个东西其实可以看做是 $A$ 对于 $B$ 内的每一个点平移的并集。我们可以清楚的看到这个并集的形状是一个凸包，而且这个凸包内的所有的边都属于原来的 $A$ 和 $B$ 。注意这一点，这个性质很重要。当我们求出凸包 $A$ 和凸包 $B$ 后，按照凸包上的点滚一遍就能拥有凸包 $A$ 和凸包 $B$ 的所有边关于这个凸包最左面的点的角度的排序，接下来仿照归并排序的方式，把这些边按照角度顺序加入，就可以得到答案集合的所有点。这些点虽然是按顺序加入的，但是最后不一定是一个凸包，所以再求一遍就好了。现在要做的全部事情已经很显然了。 如果把 $A+B$ 定义为 $\{a+b|(a\in A,b\in B)\}$，这个东西实际上叫做`Minkowski sum`。~~我并不知道这是个什么东西也不会~~ 代码是~~抄~~仿照了[别的大佬的](https://blog.csdn.net/cdsszjj/article/details/80392221)(不过是我自己写的QAQ) 代码里的注释还是蛮详细的 ~~压行阅读无能？Astyle了解一下~~ ```cpp // luogu-judger-enable-o2 #include <bits/stdc++.h> #define rap(i,s,n) for(int i=s;i<=n;i++) #define drap(i,n,s) for(int i=n;i>=s;i--) #define N 111111 #define ll long long #define lf double #define m(s,k) memset(s,k,sizeof s) using namespace std; char xB[1<<15],*xS=xB,*xTT=xB; #define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++) #define isd(c) ((c>='0'&&c<='9')||(c=='-')) template<typename T> inline bool rd(T& xa){ char xchh; T f=1; while(xchh=getc(),(!isd(xchh))&&(xchh!=0)); if(xchh==0) return 0; if(xchh=='-') xchh=getc(),f=-1; xa=xchh-'0'; while(xchh=getc(),isd(xchh)) xa=xa*10+xchh-'0'; xa*=f; return 1; }//读入优化不用管 struct point{ ll x,y; point(){} point(ll _,ll __):x(_),y(__){} point operator + (const point& b) const {return point(x+b.x,y+b.y);} point operator - (const point& b) const {return point(x-b.x,y-b.y);}//顾名思义的加减 ll operator * (const point& b) const {return x*b.y-y*b.x;} //这个X乘，a x b如果小于0说明b在a的右面，否则b在a的左面。如果x为0说明a与b平行。 }t[N*2],p[N*2],p1[N],p2[N],v1[N],v2[N]; //大家都知道点和向量其实是一样的 所以这个point又是point又是vector 其中t,p,p1,p2是点，v1v2是向量 ll len(point a){return a.x*a.x+a.y*a.y;} point tss;//随便写的... bool cmp(const point& a,const point& b){ ll k=(a-tss)*(b-tss); if(k) return k>0; else return len(a-tss)<len(b-tss); }//因为差积可以判断左右 int graham(point *a,int n){ rap(i,1,n) t[i]=a[i]; rap(i,2,n) if(t[i].x<t[1].x||(t[i].x==t[1].x&&t[i].y<t[1].y)) swap(t[1],t[i]); tss=t[1]; sort(t+2,t+n+1,cmp); int top=1; rap(i,2,n){ while(top>1&&(t[top]-t[top-1])*(t[i]-t[top-1])<=0) top--; t[++top]=t[i]; //保证从开始的点出来是一个不断左转的过程 } rap(i,1,top) a[i]=t[i]; return top; //求凸包 } int n,m,q,cnt; bool init(point x){ //init=in it?判断是否在里面 并不是初始化(233) point vx=x-p[1]; if(vx*(p[cnt]-p[1])<0||vx*(p[2]-p[1])>0) return 0; long int px=lower_bound(p+2,p+cnt+1,x,cmp)-p-1; //按照排序规则直接二分搞出它的下面的点 //开始的时候忘了后面的-1WA了N发(MDZZ) return (x-p[px])*(p[px%cnt+1]-p[px])<=0; } int main(){ rd(n); rd(m); rd(q); rap(i,1,n) rd(p1[i].x),rd(p1[i].y); n=Graham(p1,n); rap(i,1,m) rd(p2[i].x),rd(p2[i].y),p2[i].x=-p2[i].x,p2[i].y=-p2[i].y; m=Graham(p2,m); //注意取反 rap(i,1,n-1) v1[i]=p1[i+1]-p1[i]; v1[n]=p1[1]-p1[n]; rap(i,1,m-1) v2[i]=p2[i+1]-p2[i]; v2[m]=p2[1]-p2[m]; //搞出所有的线段 p[1]=p1[1]+p2[1]; cnt=1; int l1=1,l2=1; while(l1<=n&&l2<=m) ++cnt,p[cnt]=p[cnt-1]+((v1[l1]*v2[l2]>=0)?(v1[l1++]):(v2[l2++])); while(l1<=n) ++cnt,p[cnt]=p[cnt-1]+v1[l1++]; while(l2<=m) ++cnt,p[cnt]=p[cnt-1]+v2[l2++]; //参照归并排序 while(cnt>1&&(p[cnt]-p[cnt-1])*(p[1]-p[cnt-1])<=0) cnt--; //因为后面有一些无用点 直接做凸包也可以不过这样常数小 tss=p[1]; point qx; rap(i,1,q) rd(qx.x),rd(qx.y),printf("%d\n",init(qx)); return 0; } ```