题解 P4557 【[JSOI2018]战争】

WinXP · 2018-07-06 15:41:58 · 题解

~~写题解写到一半不小心弄没了体验极差~~

所以首先我们可以发现这是一道可怜计算几何题

首先有个重点，题目说的是存在平面上的任何一个点被两个部落包含是不合法情况，而不是(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。~~我并不知道这是个什么东西也不会~~ 代码是抄仿照了别的大佬的(不过是我自己写的QAQ)

代码里的注释还是蛮详细的

~~压行阅读无能？Astyle了解一下~~

// 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;
}