题面

http://loj.ac/problem/2549

题解

前置知识

• 闵可夫斯基和：https://blog.csdn.net/Deep_Kevin/article/details/82592742

设第一个部落的凸包内的点的集合为A，第二个部落的凸包内的点的集合为B。

那么，平移向量P后，存在冲突即代表着\(\exist x \in A,y \in B\)，且\(x=y+p\)。因此，由闵可夫斯基和的定义，存在冲突等价于\(p{\in}A+(-B)\)，其中\(-B\)指的是\(B\)关于原点进行中心对称后的图形。

判断一个点\((dx,dy)\)是否在一个凸包内部，只需要将这个凸包分为左右两半，找到直线\(y=dy\)与左右凸包的交点所在的线段，然后判叉积即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define N 100000
#define rg register
#define In inline
#define ll long long
#define eps 1e-8

In ll read(){
    ll s = 0,ww = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
    while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
    return s * ww;
}

In ll sgn(double x){
    if(x < -eps)return -1;
    return x > eps;
}

struct vec{
    ll x,y;
    vec(){}
    vec(ll _x,ll _y){x = _x,y = _y;}
    In friend vec operator + (vec a,vec b){
        return vec(a.x + b.x,a.y + b.y);
    }
    In friend vec operator - (vec a,vec b){
        return vec(a.x - b.x,a.y - b.y);
    }
    In friend ll Dot(vec a,vec b){
        return a.x * b.x + a.y * b.y;
    }
    In friend ll Cross(vec a,vec b){
        return a.x * b.y - a.y * b.x;
    }
    In friend double ang(vec a){
        return atan2(a.y,a.x);
    }
};

In bool samedir(vec a,vec b){return Cross(a,b) == 0 && Dot(a,b) > 0;}

In bool cmp(vec a,vec b){
    if(a.y == b.y)return a.x < b.x;
    else return a.y > b.y;
}

ll n,m,q,mid;
vec A[N+5],B[N+5],H[2*N+5];
vector<vec>H1,H2;

In bool check(vec a,vec b,vec c){
    return Cross(c - b,a - b) > 0;
}

void calcCH(vec *A,ll n,vector<vec>&H){
    sort(A + 1,A + n + 1,cmp);
    for(rg int i = 1;i <= n;i++){
        while(H.size() > 1 && !check(H[H.size()-2],H[H.size()-1],A[i]))H.pop_back();
        H.push_back(A[i]);  
    }
    int m = H.size();
    for(rg int i = n;i >= 1;i--){
        while(H.size() > m && !check(H[H.size()-2],H[H.size()-1],A[i]))H.pop_back();
        H.push_back(A[i]);
    }
    H.pop_back();
}

vec l1[N+5],l2[N+5];
vector<vec>l;
ll Hn;

void mink(){
    int n = H1.size(),m = H2.size();
    for(rg int i = 0;i < n - 1;i++)l1[i] = H1[i+1] - H1[i];l1[n-1] = H1[0] - H1[n-1];
    for(rg int i = 0;i < m - 1;i++)l2[i] = H2[i+1] - H2[i];l2[m-1] = H2[0] - H2[m-1];
    int j = -1;
    for(rg int i = 0;i < n;i++){
        double Ang = ang(l1[i]);
        while(j < m - 1 && ang(l2[j+1]) < Ang)j++,l.push_back(l2[j]);
        l.push_back(l1[i]);
    }
    while(j < m - 1)j++,l.push_back(l2[j]);
    ll cur = 0;
    for(rg int i = 0;i < l.size();i++)
        if(i && samedir(l[i],l[i-1])){
            l[cur-1] = l[cur-1] + l[i];
        }
        else l[cur++] = l[i];
    Hn = cur;
    l.resize(Hn);
    H[0] = H1[0] + H2[0];
    for(rg int i = 0;i < Hn - 1;i++)H[i+1] = H[i] + l[i];
    for(rg int i = 0;i < l.size();i++)if(sgn(ang(l[i])) > 0){
        mid = i;break;
    }
}

In bool cmp2(vec a,vec b){return a.y >= b.y;}

In bool cmp3(vec a,vec b){return a.y <= b.y;}

In bool judge(int i,vec a){
    return Cross(l[i],a - H[i]) >= 0;
}

bool solve(vec a){
    if(a.y > H[0].y || a.y < H[mid].y)return 0;
    if(a.y == H[0].y){
        int L = H[0].x,R = H[Hn-1].y == H[0].y ? H[Hn-1].x : L;
        return L <= a.x && a.x <= R;
    }
    if(a.y == H[mid].y){
        int R = H[mid].x,L = H[mid-1].y == H[mid].y ? H[mid-1].x : R;
        return L <= a.x && a.x <= R;
    }
    int i;
    i = upper_bound(H,H + mid,a,cmp2) - H - 1;if(!judge(i,a))return 0;
    i = upper_bound(H + mid,H + Hn,a,cmp3) - H - 1;if(!judge(i,a))return 0;
    return 1;
}

int main(){
    n = read(),m = read(),q = read();
    for(rg int i = 1;i <= n;i++){
        int x = read(),y = read();
        A[i] = vec(x,y);
    }
    calcCH(A,n,H1);
    for(rg int i = 1;i <= m;i++){
        int x = read(),y = read();
        B[i] = vec(-x,-y);
    }
    calcCH(B,m,H2);
    mink();
    while(q--){
        int x = read(),y = read();
        puts(solve(vec(x,y)) ? "1" : "0");
    }
    return 0;
}

[JSOI2018][LOJ2549][洛谷P4557]战争(闵可夫斯基和）

原文：https://www.cnblogs.com/xh092113/p/12326043.html