题解（只因看不懂楼上的）

闵可夫斯基和
一、概述
学习此内容需一定计算几何基础，出门右拐：https://www.cnblogs.com/xzyxzy/p/10033130.html

官方定义：两个图形A,B的闵可夫斯基和C={a+b∣a∈A,b∈B}

通俗一点：从原点向图形A内部的每一个点做向量，将图形B沿每个向量移动，所有的最终位置的并便是闵可夫斯基和

由于博主太菜，本文只讨论凸包的闵可夫斯基和

如下图，粉色区域便是三角形和一个不规则四边形的闵可夫斯基和

二、怎么求
利用瞪眼法得，闵可夫斯基和的边是由两凸包构成的

也就是说把两凸包的边极角排序后直接顺次连起来就是闵可夫斯基和

由于凸包的优美性质，直接归并排序就好了

但是需要注意的是可能会有三点共线的情况，于是再扔过去重新求一次凸包就好了

三、应用举例
题目
[JSOI2018]战争

两个凸包A,B，移动B，问是否还有交点。n≤10的五次方 ,q≤10 的五次方

正解
令a∈A,b∈B则移动向量w使得存在b+w=a

那么w需要满足w=a−b

构造闵可夫斯基和C={a+(−b)}

在输入B的时候横纵坐标都取反即可

余下问题便是判断输入的移动向量是否在C内，计算几何有讲
代码
我觉得这题值这个黑色标签

不是很好转换，有点策不清

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const ll N=1e5+10;
struct Node
{
	ll x,y;
	Node operator - (Node A) {return (Node){x-A.x,y-A.y};}
	Node operator + (Node A) {return (Node){x+A.x,y+A.y};}
	ll operator * (Node A) const {return x*A.y-y*A.x;}
	ll len() const {return x*x+y*y;}
}A[N],C1[N],C2[N],s1[N],s2[N],bs;
ll cmp1(const Node&A,const Node&B) {return A.y<B.y||(A.y==B.y&&A.x<B.x);}
ll cmp2(const Node&A,const Node&B) {return A*B>0||(A*B==0&&A.len()<B.len());}
ll n,m,sta[N],top,q,tot;
void Convex(Node *A,ll &n)
{
	sort(A+1,A+n+1,cmp1);
	bs=A[1];sta[top=1]=1;
	for(ll i=1;i<=n;i++) A[i]=A[i]-bs;
	sort(A+2,A+n+1,cmp2);
	for(ll i=2;i<=n;sta[++top]=i,i++)
		while(top>=2&&(A[i]-A[sta[top-1]])*(A[sta[top]]-A[sta[top-1]])>=0) top--;
	for(ll i=1;i<=top;i++) A[i]=A[sta[i]]+bs;
	n=top;A[n+1]=A[1];
}
void Minkowski()
{
	for(ll i=1;i<n;i++) s1[i]=C1[i+1]-C1[i];s1[n]=C1[1]-C1[n];
	for(ll i=1;i<m;i++) s2[i]=C2[i+1]-C2[i];s2[m]=C2[1]-C2[m];
	A[tot=1]=C1[1]+C2[1];
	ll p1=1,p2=1;
	while(p1<=n&&p2<=m) ++tot,A[tot]=A[tot-1]+(s1[p1]*s2[p2]>=0?s1[p1++]:s2[p2++]);
	while(p1<=n) ++tot,A[tot]=A[tot-1]+s1[p1++];
	while(p2<=m) ++tot,A[tot]=A[tot-1]+s2[p2++];
}
ll in(Node a)
{
	if(a*A[1]>0||A[tot]*a>0) return 0;
	ll ps=lower_bound(A+1,A+tot+1,a,cmp2)-A-1;
	return (a-A[ps])*(A[ps%tot+1]-A[ps])<=0;
}
int main()
{
	cin>>n>>m>>q;
	for(ll i=1;i<=n;i++)
		scanf("%lld%lld",&C1[i].x,&C1[i].y);
	Convex(C1,n);
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld",&C2[i].x,&C2[i].y);
		C2[i].x=-C2[i].x;C2[i].y=-C2[i].y;
	}
	Convex(C2,m);
	Minkowski();
	Convex(A,tot);
	bs=A[1];for(ll i=tot;i>=1;i--) A[i]=A[i]-A[1];
	while(q--)
	{
		scanf("%lld%lld",&A[0].x,&A[0].y);
		printf("%lld\n",in(A[0]-bs));
	}
	return 0;
}

代码2：

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

struct P {
    ll x, y;
    P() {}
    P(ll _x, ll _y): x(_x), y(_y) {}
    P operator + (const P& o) const { return P(x+o.x, y+o.y); }
    P operator - (const P& o) const { return P(x-o.x, y-o.y); }
    bool operator < (const P& o) const { return x < o.x || (x==o.x && y < o.y); }
    bool operator == (const P& o) const { return x==o.x && y==o.y; }
};

ll cross(const P& a, const P& b) { return a.x*b.y - a.y*b.x; }
ll cross(const P& o, const P& a, const P& b) { return cross(a - o, b - o); }

vector<P> convexHull(vector<P>& pts) {
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    int n = pts.size();
    if (n <= 1) return pts;
    vector<P> lower, upper;
    for (int i = 0; i < n; ++i) {
        while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), pts[i]) <= 0) lower.pop_back();
        lower.push_back(pts[i]);
    }
    for (int i = n-1; i >= 0; --i) {
        while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), pts[i]) <= 0) upper.pop_back();
        upper.push_back(pts[i]);
    }
    lower.pop_back();
    upper.pop_back();
    vector<P> hull = lower;
    hull.insert(hull.end(), upper.begin(), upper.end());
    if (hull.empty() && !pts.empty()) hull.push_back(pts[0]);
    return hull;
}
void rotateToMin(vector<P>& a) {
    int n = a.size();
    if (n==0) return;
    int id = 0;
    for (int i = 1; i < n; ++i) if (a[i] < a[id]) id = i;
    rotate(a.begin(), a.begin()+id, a.end());
}
vector<P> minkowskiSum(vector<P> A, vector<P> B) {
    if (A.empty() || B.empty()) return {};
    rotateToMin(A);
    rotateToMin(B);
    int na = A.size(), nb = B.size();
    vector<P> ea(na), eb(nb);
    for (int i = 0; i < na; ++i) ea[i] = A[(i+1)%na] - A[i];
    for (int i = 0; i < nb; ++i) eb[i] = B[(i+1)%nb] - B[i];
    int ia = 0, ib = 0;
    P cur = A[0] + B[0];
    vector<P> C;
    C.push_back(cur);
    while (ia < na || ib < nb) {
        if (ia == na) {
            cur = cur + eb[ib++];
            C.push_back(cur);
            continue;
        }
        if (ib == nb) {
            cur = cur + ea[ia++];
            C.push_back(cur);
            continue;
        }
        ll cr = cross(ea[ia], eb[ib]);
        if (cr > 0) {
            cur = cur + ea[ia++];
            C.push_back(cur);
        } else if (cr < 0) {
            cur = cur + eb[ib++];
            C.push_back(cur);
        } else {
            cur = cur + ea[ia] + eb[ib];
            ia++; ib++;
            C.push_back(cur);
        }
    }
    if (C.size() > 1 && C.front() == C.back()) C.pop_back();
    vector<P> res;
    for (auto &p : C) {
        if (res.empty() || !(res.back() == p)) res.push_back(p);
    }
    vector<P> res2;
    for (size_t i = 0; i < res.size(); ++i) {
        P a = res[i];
        P b = res[(i+1)%res.size()];
        P c = res[(i+2)%res.size()];
        if (res2.size() < 2) res2.push_back(a);
        else {
            while (res2.size() >= 2) {
                P p1 = res2[res2.size()-2], p2 = res2[res2.size()-1];
                if (cross(p1, p2, a) == 0) res2.pop_back();
                else break;
            }
            res2.push_back(a);
        }
    }
    if (res2.empty()) return res;
    return res2;
}
bool onSegment(const P& a, const P& b, const P& p) {
    if (cross(a,b,p) != 0) return false;
    ll minx = min(a.x,b.x), maxx = max(a.x,b.x);
    ll miny = min(a.y,b.y), maxy = max(a.y,b.y);
    return p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy;
}
bool pointInConvex(const vector<P>& a, const P& p) {
    int n = a.size();
    if (n == 0) return false;
    if (n == 1) return a[0] == p;
    if (n == 2) return onSegment(a[0], a[1], p);
    ll c1 = cross(a[0], a[1], p);
    ll c2 = cross(a[0], a[n-1], p);
    if (c1 < 0) return false;
    if (c2 > 0) return false;
    int l = 1, r = n-1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (cross(a[0], a[mid], p) >= 0) l = mid;
        else r = mid;
    }
    ll area = llabs(cross(a[0], a[l], a[l+1]));
    ll s1 = llabs(cross(p, a[0], a[l]));
    ll s2 = llabs(cross(p, a[l], a[l+1]));
    ll s3 = llabs(cross(p, a[l+1], a[0]));
    return (s1 + s2 + s3 == area);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;
    vector<P> Apts(n), Bpts(m);
    for (int i = 0; i < n; ++i) cin >> Apts[i].x >> Apts[i].y;
    for (int i = 0; i < m; ++i) cin >> Bpts[i].x >> Bpts[i].y;
    vector<P> queries(q);
    for (int i = 0; i < q; ++i) cin >> queries[i].x >> queries[i].y;
    vector<P> A = convexHull(Apts);
    vector<P> B = convexHull(Bpts);

    for (auto &p : B) p.x = -p.x, p.y = -p.y;   
    vector<P> C = minkowskiSum(A, B);
    for (int i = 0; i < q; ++i) {
        bool inside = pointInConvex(C, queries[i]);
        cout << (inside ? 1 : 0) << '\n';
    }
}