JSOI2018 战争

大意

为了阻止战争,你就是,天选之人~~

解析

假设$a\in A,b\in B$,存在向量$w$,使得$b+w=a$,那么根据闵可夫斯基差,可以得到$A-B=\{w\rvert w+B\subseteq A\}$
当然,解题都是怎么方便怎么来,我们直接将$B$取反,然后和$A$求个闵可夫斯基和就完事了.
最后再判断所给点在不在C里,就完事了
哦,要对$A,B$进行一次求凸包,去掉边上的点
然后再对$C$求一次.

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;
const double pi = acos(-1.0);
const double inf = 1e100;
const double eps = 1e-12;
typedef struct point vec; //向量vec
struct point { //点的基本数据结构
    double x, y;
    double poe;
    point(double _x = 0, double _y = 0)
        : x(_x)
        , y(_y)
    {
    }

    double len() //向量模长的平方
    {
        return x * x + y * y;
    }
    double operator*(const point& i_T) const //点积
    {
        return x * i_T.x + y * i_T.y;
    }
    double operator^(const point& i_T) const //叉积
    {
        return x * i_T.y - y * i_T.x;
    }
    point operator*(double u) const
    {
        return point(x * u, y * u);
    }
    bool operator==(const point& i_T) const
    {
        return x == i_T.x && y == i_T.y;
    }
    point operator/(double u) const
    {
        return point(x / u, y / u);
    }
    point operator+(const point& i_T)
    {
        return point(x + i_T.x, y + i_T.y);
    }
    point operator-(const point& i_T)
    {
        return point(x - i_T.x, y - i_T.y);
    }
    friend bool operator<(point a, point b)
    {
        return fabs(a.y - b.y) < eps ? a.x < b.x : a.y < b.y;
    }
    void atn2()
    {
        poe = atan2(y, x);
    }
    friend ostream& operator<<(ostream& out, point& a)
    {
        //cout << a.x << ' ' << a.y;
        printf("%.0f %.0f", a.x, a.y);
        return out;
    }
    friend istream& operator>>(istream& in, point& a)
    {
        scanf("%lf%lf", &a.x, &a.y);
        return in;
    }
};
int bijiao(double x, double y)
{
    if (fabs(x - y) < eps)
        return 0;
    if (x > y)
        return 1;
    return -1;
}
bool cmp(vec a, vec b)
{
    return bijiao(a.poe, b.poe) == 0 ? (a ^ b) >= 0 : a.poe < b.poe;
}
double xuanzhuan(vec a, vec b, vec c) //求三点叉积
{
    return (b - a) ^ (c - a);
}
void Andrew(int& tail, point cl[], int n, point ql[]) //求凸包
{
    sort(cl + 1, cl + 1 + n);
    tail = 1;
    ql[1] = cl[1];
    for (int i = 2; i <= n; i++) {
        while (tail > 1 && xuanzhuan(ql[tail - 1], ql[tail], cl[i]) <= 0)
            tail--;
        ql[++tail] = cl[i];
    }
    int basic = tail;
    for (int i = n - 1; i >= 1; i--) {
        while (tail > basic && xuanzhuan(ql[tail - 1], ql[tail], cl[i]) <= 0)
            tail--;
        ql[++tail] = cl[i];
    }
}
void Minkefusiji(point s[], int& cnt, point pl1[], int tail1, point pl2[], int tail2)
{
    s[cnt = 1] = pl1[1] + pl2[1];
    for (int i = 1; i <= tail1; i++)
        pl1[i] = pl1[i + 1] - pl1[i];
    for (int i = 1; i <= tail2; i++)
        pl2[i] = pl2[i + 1] - pl2[i];
    int a1 = 1, a2 = 1;
    while (a1 <= tail1 && a2 <= tail2) {
        ++cnt;
        if ((pl1[a1] ^ pl2[a2]) >= 0)
            s[cnt] = s[cnt - 1] + pl1[a1++];
        else
            s[cnt] = s[cnt - 1] + pl2[a2++];
    }
    while (a1 <= tail1)
        ++cnt, s[cnt] = s[cnt - 1] + pl1[a1++];
    while (a2 <= tail2)
        ++cnt, s[cnt] = s[cnt - 1] + pl2[a2++];
}
bool cmp2(point A, point B)
{
    return (A ^ B) > 0 || ((A ^ B) == 0 && A.len() < B.len());
}
bool dian_in_tubao(point a, point p[], int tail)    //包含边界
{
    if ((a ^ p[1]) > 0 || (p[tail] ^ a) > 0)
        return false;
    int ps = lower_bound(p + 1, p + tail + 1, a, cmp2) - p - 1;
    return ((a - p[ps]) ^ (p[ps % tail + 1] - p[ps])) <= 0;
}
point p[MAXN], q2[MAXN], q1[MAXN];
int main()
{
    int m, n, q;
    cin >> m >> n >> q;
    for (int i = 1; i <= m; i++)
        cin >> p[i];
    int tail1;
    Andrew(tail1, p, m, q1);

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        p[i].x = -p[i].x, p[i].y = -p[i].y;
    }
    int tail2;
    Andrew(tail2, p, n, q2);
    tail1--, tail2--;

    int cnt, tail;
    Minkefusiji(p, cnt, q1, tail1, q2, tail2);

    Andrew(tail, p, cnt, q1);
    tail--;
    point bs = q1[1];
    for (int i = 1; i <= tail; i++)
        q1[i] = q1[i] - bs;
    while (q--) {
        point pi;
        cin >> pi;
        if (dian_in_tubao(pi - bs, q1, tail))
            cout << 1 << endl;
        else
            cout << 0 << endl;
    }
    return 0;
}