Luogu p4557 [jsoi2018] war

https://www.luogu.com.cn/problem/P4557

Give two convex hulls $A,B$, Make $a\in A,b\in B$, If there is $b+v=a$, that $v$ This vector will conflict

Transpose available
$v=a-b$, Then it becomes judgment $v$ Whether in $A-B$ in

hold $A,B$ Find Minkowski and , Then judge

The specific process is first to $A,B$ Separate convex hull , Throw away the useless points

Then select the lowest point of the two convex hulls , Add it up as a starting point , When we express the edges of two convex hulls with vectors , Find the convex hull again

No particular details

code:

#include<bits/stdc++.h>
#define N 200060
#define ll long long
using namespace std;
struct A {
    
    ll x, y;
    A operator + (const A &o) const {
    return (A){
    x + o.x, y + o.y};}
    A operator - (const A &o) const {
    return (A){
    x - o.x, y - o.y};}
    ll operator * (const A &o) const {
    return x * o.y - y * o.x;}
    ll len() {
    return x * x + y * y;}
};
A vec(A x, A y) {
    
    return y - x;
}

int cmpp(A x, A y) {
    
    if(x.y != y.y) return x.y < y.y;
    return x.x < y.x;
}
A bs;
int cmp(A x, A y) {
    
    ll o = vec(bs, x) * vec(bs, y);
    if(o > 0) return 1;
    return o == 0 && vec(bs, x).len() < vec(bs, y).len();
}

int sta[N << 1];
void get(A *a, int &n) {
    
    sort(a + 1, a + 1 + n, cmpp);
    bs = a[1];
    sort(a + 1 ,a + 1 + n, cmp);
    int top = 0;
    for(int i = 1; i <= n; i ++) {
    
        while(top > 1 && vec(a[sta[top - 1]], a[i]) * vec(a[sta[top - 1]], a[sta[top]]) >= 0) top --;
        sta[++ top] = i;
    }
    for(int i = 1; i <= top; i ++) a[i] = a[sta[i]];
    n = top; a[n + 1] = a[1];
}

int n, m, q, gs;
A a[N], b[N], c[N], v1[N], v2[N];
void Mink() {
    
    for(int i = 1; i <= n; i ++) v1[i] = vec(a[i], a[i + 1]);
    for(int i = 1; i <= m; i ++) v2[i] = vec(b[i], b[i + 1]);

    c[gs = 1] = a[1] + b[1];
    int p1 = 1, p2 = 1;
    while(p1 <= n && p2 <= m) 
        ++ gs, c[gs] = c[gs - 1] + (v1[p1] * v2[p2] >= 0? v1[p1 ++] : v2[p2 ++]);
    while(p1 <= n) 
        ++ gs, c[gs] = c[gs - 1] + v1[p1 ++];
    while(p2 <= n)
        ++ gs, c[gs] = c[gs - 1] + v2[p2 ++];
}
int in(A x) {
    
    if(vec(c[1], c[gs]) * vec(c[1], x) > 0) return 0;
    if(vec(c[1], x) * vec(c[1], c[2]) > 0) return 0;

    int pos = lower_bound(c + 1, c + 1 + gs, x, cmp) - c - 1;
    return vec(c[pos], c[pos % gs + 1]) * vec(c[pos], x) >= 0;
}
int main() {
    
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++) scanf("%lld%lld", &a[i].x, &a[i].y);
    get(a, n);
    for(int i = 1; i <= m; i ++) scanf("%lld%lld", &b[i].x, &b[i].y), b[i].x *= -1, b[i].y *= -1;
    get(b, m);
    Mink();
    get(c, gs);

    while(q --) {
    
        A x;
        scanf("%lld%lld", &x.x, &x.y);
        printf("%d\n", in(x));
    }
    return 0;
}