题解 P4557 【[JSOI2018]战争】

· · 题解

大概是JSOI2018不算难的一题吧（这是我A的第3道JSOI2018的题）。因为我是看了另一个题解的思路才会做的，所以不知道想到正解有多难。但可以肯定的是，实现起来难度不大，但有一些细节需要注意。

这题大概是紫题难度，别被黑标签吓到。（尽管我愉快地贡献了近10次提交）

预备知识：向量，凸包，数学技巧 （没错就这么简单）

题意：给定凸包α和β，大小分别为n,m，q次询问将β平移\vec{d}后是否与α有交。n,m,q均为10^5级别。

先求2个点集的凸包肯定没问题吧。听说Andrew比Graham常数小，还有一个复杂度最优的Melkman，用起来有点麻烦。

由于询问较多，每次进行凸包判交复杂度很大（而且我不会判交），所以考虑先处理出可行域（即会导致两个凸包相交的向量\vec{OP}的点P形成的区域）。

我能想到的类似的问题就是线性规划，求(x,y)是否满足约束条件。做法可以是先处理出可行域（凸包），看点是否在凸包上而不用逐个判断是否符合约束条件。

我们以这两个凸包为例（造数据建议保证2个凸包边尽量不平行，棱角分明，这样容易看出来点性质）

不可行域长啥样？先画图看看呗（如果手头没有好的绘图工具，ppt也可，效果比windows painter好）。我们只需要找出临界位置（这点类似线性规划），图中用灰色表示（应该有(n+m)个）。显然，将灰色凸包沿着α的边平移即可得到更完整的可行区域。

在β上取一点A，设它在平移得到的凸包上的对应点为A_i（这些点都在可行域上，且是可行域的顶点），可以得到一个由这些点构成的凸包。关于这是凸包，应该可以用半平面交证明（我没证过）。

将凸包转化成\vec{OP}的点P形成的区域，只需将凸包平移\vec{AO}。

接下来我们来分析这个凸包γ的特点。因为有点A_i沿α的边平移形成边，所以γ的边包含α的边（当然位置不一样）。灰色三角形在α的某些顶点处，需要平移自身的一条边的长度才能绕过去，所以γ的边也包含β的边。因此，γ由α和β的边组成，各顶点的坐标，则由来自α和β的对应点的坐标相加而成。如果眼力够好，这些是可以瞪出来的。

接下来考虑如何合并两个凸包。

根据凸包的性质，按逆时针顺序各边向量的方向角是单调的，所以只需要将组成α和β的边按方向角排序就可以了。但一定要这么做吗？考虑到求完凸包后α和β的边的方向角都是单调的，可以直接用类似归并的方法。（不懂方向角？见任意角的定义）

可以将β取反，这样加边就是顺着的，也许更方便？

初始置入两个凸包的首个点。假设接下来待加的两个凸包的点分别为A_i和B_j（0 \le i \lt n, 0 \le j \lt m，初始i,j都为1，这里n,m是实际点数+1），比较\vec{A_i}-\vec{A_{i-1}}和\vec{B_j}-\vec{B_{j-1}}，如果前者方向角小，则向γ加入点C_{i+j-1}=A_i+B_{j-1}，反之加入点C_{i+j-1}=A_{i-1}+B_j。（这里是对β取反后的）比较可以用叉积来做。注意如果一个凸包已经加完，就不用判大小关系了。设合并得到的凸包大小为N (N=n+m-1)，依旧将第一个点计2次。

到这里实际上已经70分了。对每次询问直接O(N)判点是否在凸包内（含边界）。

接下来要面对的是如何用logN的复杂度完成查询操作。

如上图，绿线为查询的向量P(dx,dy)的纵坐标所在直线，它与凸包边有最多2个交点。显然只有图中特意标出来的2条蓝边决定点P是否在凸包内。由于顶点的纵坐标单调，可以lower_bound二分出线段的2个端点（将凸包包划分为左凸壳和右凸壳，在两个下标区间内分别二分，注意由于单调性不同所以cmp不同）。然后上叉积即可。 我相信我的做法是最烂的

Q1：如果绿线（不与任何一条边共线）恰好过一个顶点，那么该是哪两个点？

A1：都一样，P与某一端点重合，叉积为0，判点在凸包内。

Q2：如果绿线与某条边平行，该如何处理？

A2：显然这条边是凸包最上面或最下面的边。直接lower_bound，我是能处理和下边共线的情况的，只需要特判上边。很简单，记录凸包顶部的坐标范围，对于y与上边共线的情况，只判x是否在区间里就行了。如果不放心，也可以特判下边。我不特判只有80pts。

这样100pts就拿到了。

总之这题关键是思想，细节部分真的不难，自己推一遍会发现很简单。

还有注意开ll，坐标没有小数据，没ll就爆0。（我一开始注意到了结果还是忘开于是愉快爆了）。不涉及小数，所以不需要考虑精度误差。注意凸包大小不要搞混。

我代码应该还行吧。

#include <cstdio>
#include <algorithm>
#include <functional>
#define reg register
using namespace std;
typedef long long ll;
const int MAXN=100010;
int n0,m0,n,m,N,Q; //原始点集大小，2个凸包大小，可行域凸包大小
struct point {
    int x,y;
    point() {}
    point(double X,double Y):x(X),y(Y) {}
} a0[MAXN],b0[MAXN],a[MAXN],b[MAXN],c[MAXN*2]; //原点集数组，2个凸包，可行域凸包
int high,high0; //最高点的下标
inline point operator +(const point &p1,const point &p2)  {
    return point(p1.x+p2.x,p1.y+p2.y);
}
inline point operator -(const point &p1,const point &p2)  {
    return point(p1.x-p2.x,p1.y-p2.y);
}
inline ll operator *(const point &p1,const point &p2) { //向量叉积，注意ll
    return (ll)p1.x*p2.y-(ll)p1.y*p2.x;
}
inline bool operator <(const point &p1,const point &p2)  {
    return p1.y<p2.y || p1.y==p2.y && p1.x<p2.x;
}
inline bool operator >(const point &p1,const point &p2) {
    return p1.y>p2.y;
}
int Andrew(int n,point a[],point sta[]) { //求凸包，返回凸包大小+1
    sort(a,a+n);
    int top=0;
    for (reg int i=0;i<n;i++) {
        while (top>1 && (sta[top-1]-sta[top-2])*(a[i]-sta[top-2])<=0) top--;
        sta[top++]=a[i];
    }
    int k=top;
    for (reg int i=n-2;i>=0;i--) {
        while (top>k && (sta[top-1]-sta[top-2])*(a[i]-sta[top-2])<=0) top--;
        sta[top++]=a[i];
    }
    return top;
}
void merge() { //合并凸包，求出不合法向量范围
    N=m+n-1;
    int i=1,j=1; //当前待选的点
    c[0]=a[0]+b[0];
    high=high0=0; //最高点的区间上界和下界
    //类似归并，按方向角顺序加入新凸包，方向角用
    for (reg int k=1;k<N;k++) {
        c[k]= i<n && (j==m || (a[i]-a[i-1])*(b[j]-b[j-1])>0) ? a[i++]+b[j-1] : a[i-1]+b[j++];
        if (c[k].y>c[high].y) high=k;
        if (c[k].y>=c[high].y) high=k;
    }
}
bool query(const point &p) { //判断点p是否在凸包内（含边界）
    if (p.y<c[0].y || p.y>c[high].y || p.y==c[high].y && (p.x<c[high].x || p.x>c[high0].x)) return false;
    //上面先特判一定在凸包外，和在顶部线段外的情况（因为下面的无法处理这种情况）
    point *p1=lower_bound(c,c+high,p),*p2=lower_bound(c+high,c+N,p,greater<point>()); //按y找所在位置
    return (p-*(p1-1))*(*p1-p)<=0 && (p-*(p2-1))*(*p2-p)<=0;
}
int main() {
    scanf("%d%d%d",&n0,&m0,&Q);
    for (reg int i=0;i<n0;i++) scanf("%d%d",&a0[i].x,&a0[i].y);
    for (reg int i=0;i<m0;i++) scanf("%d%d",&b0[i].x,&b0[i].y), b0[i].x*=-1, b0[i].y*=-1;
    n=Andrew(n0,a0,a);
    m=Andrew(m0,b0,b);
    merge();
    while (Q--) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(point(x,y))); //查询，在凸包内即冲突
    }
    return 0;
}