闵可夫斯基和

闵可夫斯基和：

      闵可夫斯基和又称闵可夫斯基加法，是两个欧几里得空间的点集的和。

      点集A和点集B的闵可夫斯基和被定义为：   A+B={a+b | a属于A，属于B}

      例如，平面上有两个三角形，其坐标分别为A={(1,0),(0,1),(0,-1)}及B = {(0, 0), (1, 1), (1, −1)}，则其闵可夫斯基和为

              A + B = {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)}

     以上是百度百科的定义，通俗点讲就是讲，点集A和点集B的闵可夫斯基和就是将点集B的每个点坐标当做一个向量，然后点集A分别沿着这些向量平移，得到新的点集就是点集A与点集B的闵可夫斯基和。如下图（画图太难了，随便整了个简单的）

     设绿色部分为点集A,蓝色部分为点集B，则红色部分构成点集就是A与B的闵可夫斯基和。

                        

     例题引入：

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

     题目描述

         九条可怜是一个热爱读书的女孩子。

       在她最近正在读的一本小说中，描述了两个敌对部落之间的故事。第一个部落有 n 个人，第二个部落有 m 个人，每一个人的位置可以抽象成二维平面上坐标为 (xi​,yi​) 的点。

       在这本书中，人们有很强的领地意识，对于平面上的任何一个点，如果它被三个来自同一部落的人形成的三角形（可能退化成一条线段）包含（包括边界），那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地中，那么这两个部落就会为了争夺这一个点而发生战争。

       常年的征战让两个部落不堪重负，因此第二个部落的族长作出了一个英明的决定，他打算选择一个向量 (dx,dy) ，让所有的族人都迁徙这个向量的距离，即所有第二阵营的人的坐标都变成 (xi​+dx,yi​+dy) 。

       现在他计划了 q 个迁徙的备选方案，他想要你来帮忙对每一个迁徙方案，计算一下在完成了迁徙之后，两个部落之间还会不会因为争夺领地而发生战争。

      输入格式

      第一行输入三个整数 n,m,q，表示两个部落里的人数以及迁徙的备选方案数。

      接下来 n 行每行两个整数 xi​,yi​​​ 表示第一个部落里的人的坐标。

      接下来 m 行每行两个整数 xi​,yi​​​ 表示第二个部落里的人的坐标。

      接下来 q 行每行两个整数 dxi​,dyi​​​ 表示一个迁徙方案。

      输入数据保证所有人的坐标两两不同。

     输出格式

     对于每个迁徙方案，输出一行一个整数，0 表示不会发生冲突，1 表示会发生冲突。

     巴拉巴拉一大堆，题意其实就是给出两个点集A,B，以及q次询问。对于每次询问，给出一个向量，然后点集B向向量平移，若平移后的点集A与点集B构成的两个多边形存在交点则输出1，否则输出0。

     

    解题思路：

    对于向量 p，若点集B构成的多边形向向量 p 平移后与点集A构成的多边形存在交点，那么就可以得出： 存在 b+p=a (b属于B, a属于A)

    转化一下可以得到当A、B存在交点时，向量 p 属于{ a-b | a属于A, b属于B}

    因此我们可以来构造闵可夫斯基和：C={ a + (-b) }   (在输入B的坐标时全部取反即可）

    构造完后，问题就变成了给出q次询问，若一个给出向量在C的内部则说明存在交点，若不在则说明不存在交点。

    具体步骤：

    1、构造 A,B 的凸包

    2、求解A和-B的闵可夫斯基和C

    3、对C再求一次凸包

    4、每次询问二分判断向量是否在 C 的凸包内 (时间复杂度qlogn级别）

    AC代码：

 （傻逼scanf时少了个%，debug了两个多小时）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map> 
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef unsigned long long ULL; 
const int maxn=1e5+6;
const int mod=1e9+7;
const double pi=acos(-1.0);   
const double eps=1e-8;
struct Point{
    double x,y;
    Point(double x=0, double y=0):x(x),y(y) {};
}; 
typedef Point Vector;
Point A[maxn],B[maxn],C[maxn],v1[maxn],v2[maxn]; 
int stk[maxn];
int top=0,cnt=0; 
int sgn(double x){
    if(fabs(x)<eps)
        return 0;
    if(x<0)
        return -1;
    return 1;
}
bool operator == (const Point &a, const Point &b){
    if(sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0)
       return true;
    else 
       return false;
}
Vector operator - (Point A, Point B){
    return Vector(A.x-B.x, A.y-B.y);
}
Vector operator + (Vector A, Vector B){
    return Vector(A.x+B.x, A.y+B.y); 
} 
double Dot(Vector A,Vector B){  //锐角为正，钝角为负，直角为0 
    return A.x*B.x + A.y*B.y;  
} 
double Cross(Vector v0, Vector v1){
    return v0.x*v1.y - v0.y*v1.x;
}
double Dis(Point p1, Point p2){
    return sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y));
}
double Length(Vector t){
    return t.x*t.x+t.y*t.y;
}
bool cmp1(const Point &A,const Point &B) {
    return sgn(A.y-B.y)<0||((sgn(A.y-B.y)==0&&sgn(A.x-B.x)<0));
}
//极角排序,角度相同的则距离小的在前面 
bool cmp2(const Point &A, const Point &B){
    return sgn(Cross(A,B))>0||(sgn(Cross(A,B))==0&&sgn(Length(A)-Length(B))<0);
}
//GrahamScan算法求凸包 
void Graham(Point *lst,int &n){
    sort(lst+1,lst+n+1,cmp1);
    Point bs=lst[1];
    top=1;
    stk[top]=1;
    for(int i=1;i<=n;i++)
      lst[i]=lst[i]-bs;
    sort(lst+2, lst+n+1, cmp2);//极角排序 
    for(int i=2;i<=n;i++){
        while(top>1&&sgn(Cross(lst[i]-lst[stk[top-1]],lst[stk[top]]-lst[stk[top-1]]))>=0)
           top--;
        stk[++top]=i;  
    }
    for(int i=1;i<=top;i++)
       lst[i]=lst[stk[i]]+bs;
    n=top;
    lst[top+1]=lst[1];
    return ;
}
void Minkowski(int n,int m){    //求闵可夫斯基和 
    for(int i=1;i<=n;i++)
        v1[i]=A[i+1]-A[i];
    for(int i=1;i<=m;i++)
        v2[i]=B[i+1]-B[i];
    C[cnt=1]=A[1]+B[1];
    int p1=1,p2=1;
    while(p1<=n&&p2<=m){
        ++cnt;
        if(sgn(Cross(v1[p1],v2[p2]))>=0)
            C[cnt]=C[cnt-1]+v1[p1++];
        else 
            C[cnt]=C[cnt-1]+v2[p2++];
    }
    while(p1<=n){
        ++cnt;
        C[cnt]=C[cnt-1]+v1[p1++];
    }
    while(p2<=m){
        ++cnt;
        C[cnt]=C[cnt-1]+v2[p2++];
    }
}
int pan_PL(Point p,Point a,Point b){   //判断点是否在直线上 
    return !sgn(Cross(p-a,p-b))&&sgn(Dot(p-a,p-b))<0;
}
int in(Point *P,int n,Point a){
    if(sgn(Cross(a-P[1],P[2]-P[1]))>0||sgn(Cross(P[n]-P[1],a-P[1]))>0)
         return 0;
    if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))
         return 1;
    int l=2,r=n-1;
    while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
        int mid=l+r+1>>1;
        if(sgn(Cross(a-P[1],P[mid]-P[1]))>0)
            r=mid-1;
        else 
            l=mid;
    }
    return sgn(Cross(a-P[r],P[r+1]-P[r]))<=0;
}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
       scanf("%lf%lf",&A[i].x,&A[i].y);
    Graham(A,n);
    for(int i=1;i<=m;i++){
        scanf("%lf%lf",&B[i].x,&B[i].y);
        B[i].x=-B[i].x;
        B[i].y=-B[i].y;
    }
    Graham(B,m);
    Minkowski(n,m);
    Graham(C,cnt);
    while(q--){
        Point t;
        scanf("%lf%lf",&t.x,&t.y);
        printf("%d
",in(C,cnt,t));
    }
    return 0;
}

    CF87E Mogohu-Rea Idol:https://www.luogu.com.cn/problem/CF87E

   题目描述

    A long time ago somewhere in the depths of America existed a powerful tribe governed by the great leader Pinnie-the-Wooh. Once the tribe conquered three Maya cities. Pinnie-the-Wooh grew concerned: there had to be some control over the conquered territories. That's why he appealed to the priests of the supreme god Mogohu-Rea for help.

   The priests conveyed the god's will to him: to control these three cities he should put an idol to Mogohu-Rea — that will create a religious field over the cities. However, the idol is so powerful that it can easily drive the people around it mad unless it is balanced by exactly three sacrifice altars, placed one in each city. To balance the idol the altars should be placed so that the center of mass of the system of these three points coincided with the idol. When counting the center of mass consider that all the altars have the same mass.

   Now Pinnie-the-Wooh is thinking where to put the idol. He has a list of hills, that are suitable to put an idol there. Help him to identify on which of them you can put an idol without risking to fry off the brains of the cities' population with the religious field.

Each city has a shape of a convex polygon such that no three vertexes lie on a straight line. The cities can intersect. Each altar should be attached to the city through a special ceremony, besides, it must be situated on the city's territory (possibly at the border). Thus, there may be several altars on a city's territory, but exactly one of them will be attached to the city. The altars, the idol and the hills are points on the plane, some of them may coincide.

    The hills are taken into consideration independently from each other, the altars' location for different hills may also be different.

   输入格式

     First follow descriptions of the three cities, divided by empty lines. The descriptions are in the following format:

     The first line contains an integer nn , which represent the number of the polygon's vertexes ( 3<=n<=5·10^{4}3<=n<=5⋅104 ). Next nn lines contain two integers x_{i}xi​ , y_{i}yi​ each, they are the coordinates of the polygon's ii -th vertex in the counterclockwise order.

     After the cities' description follows the integer mm ( 1<=m<=10^{5}1<=m<=105 ), which represents the number of hills. Next mm lines each contain two integers x_{j}xj​ , y_{j}yj​ , they are the coordinates of the jj -th hill.

     All the coordinates in the input data do not exceed 5·10^{8}5⋅108 in the absolute value.

   输出格式

    For each hill print on a single line "YES" (without the quotes) or "NO" (without the quotes), depending on whether the three sacrifice altars can be put to balance the idol or not.

    题意翻译

    按逆时针顺序给出三个凸包点集 A,B,C，每次查询给出点 q，问是否存在点 a∈A,b∈B,c∈C 满足 q 为 Δabc 的重心。

     解题思路：

    若p为Δabc的重心，则由三角形重心的定义可知，p=（a+b+c）/3，因此只需要求出点集A、B、C的闵可夫斯基和D，然后判断3*p是否在D的内部即可。

     AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map> 
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef unsigned long long ULL; 
const int maxn=5e5+6;
const int mod=1e9+7;
const double pi=acos(-1.0);   
const double eps=1e-9;
struct Point{
    double x,y;
    Point(double x=0, double y=0):x(x),y(y) {};
}; 
typedef Point Vector;
Point F[maxn],p[maxn],p1[maxn],p2[maxn],p3[maxn],v1[maxn],v2[maxn]; 
int stk[maxn];
int top=0,cnt; 
int sgn(double x){
    if(fabs(x)<eps)
        return 0;
    if(x<0)
        return -1;
    return 1;
}
bool operator == (const Point &a, const Point &b){
    if(sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0)
       return true;
    else 
       return false;
}
Vector operator - (Point A, Point B){
    return Vector(A.x-B.x, A.y-B.y);
}
Vector operator + (Vector A, Vector B){
    return Vector(A.x+B.x, A.y+B.y); 
} 
//向量与常数的除法 
Vector operator / (Vector A, double p){
    return Vector(A.x/p, A.y/p);
} 
Vector operator * (Vector A, double p){
    return Vector(A.x*p, A.y*p);
} 
double Dot(Vector A,Vector B){  //锐角为正，钝角为负，直角为0 
    return A.x*B.x + A.y*B.y;  
} 
double Cross(Vector v0, Vector v1){
    return v0.x*v1.y - v0.y*v1.x;
}
double Dis(Point p1, Point p2){
    return sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y));
}
double Length(Vector t){
    return t.x*t.x+t.y*t.y;
}
bool cmp1(const Point &A,const Point &B) {
    return sgn(A.y-B.y)<0||((sgn(A.y-B.y)==0&&sgn(A.x-B.x)<0));
}
//极角排序,角度相同的则距离小的在前面 
bool cmp2(const Point &A, const Point &B){
    return sgn(Cross(A,B))>0||(sgn(Cross(A,B))==0&&sgn(Length(A)-Length(B))<0);
}
//GrahamScan算法求凸包 
void Graham(Point *lst,int &n){
    sort(lst+1,lst+n+1,cmp1);
    Point bs=lst[1];
    top=1;
    stk[top]=1;
    for(int i=1;i<=n;i++)
      lst[i]=lst[i]-bs;
    sort(lst+2, lst+n+1, cmp2);//极角排序 
    for(int i=2;i<=n;i++){
        while(top>1&&sgn(Cross(lst[i]-lst[stk[top-1]],lst[stk[top]]-lst[stk[top-1]]))>=0)
           top--;
        stk[++top]=i;  
    }
    for(int i=1;i<=top;i++)
       lst[i]=lst[stk[i]]+bs;
    n=top;
    lst[top+1]=lst[1];
    return ;
}
void Minkowski(Point *A,int n,Point *B,int m,Point *C){    //求闵可夫斯基和 
    for(int i=1;i<=n;i++)
        v1[i]=A[i+1]-A[i];
    for(int i=1;i<=m;i++)
        v2[i]=B[i+1]-B[i];
    cnt=1;
    C[cnt]=A[1]+B[1];
    int p1=1,p2=1;
    while(p1<=n&&p2<=m){
        ++cnt;
        if(sgn(Cross(v1[p1],v2[p2]))>=0)
            C[cnt]=C[cnt-1]+v1[p1++];
        else 
            C[cnt]=C[cnt-1]+v2[p2++];
    }
    while(p1<=n){
        ++cnt;
        C[cnt]=C[cnt-1]+v1[p1++];
    }
    while(p2<=m){
        ++cnt;
        C[cnt]=C[cnt-1]+v2[p2++];
    }
}
int pan_PL(Point p,Point a,Point b){
    return !sgn(Cross(p-a,p-b))&&sgn(Dot(p-a,p-b))<0;
}
int in(Point *P,int n,Point a){
    if(sgn(Cross(a-P[1],P[2]-P[1]))>0||sgn(Cross(P[n]-P[1],a-P[1]))>0)
         return 0;
    if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))
         return 1;
    int l=2,r=n-1;
    while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
        int mid=l+r+1>>1;
        if(sgn(Cross(a-P[1],P[mid]-P[1]))>0)
            r=mid-1;
        else 
            l=mid;
    }
    return sgn(Cross(a-P[r],P[r+1]-P[r]))<=0;
}
int main(){
    int n1,n2,n3;
    scanf("%d",&n1);
    for(int i=1;i<=n1;i++)
        scanf("%lf%lf",&p1[i].x,&p1[i].y);
    scanf("%d",&n2); 
    for(int i=1;i<=n2;i++)
        scanf("%lf%lf",&p2[i].x,&p2[i].y);
    scanf("%d",&n3);
    for(int i=1;i<=n3;i++)
        scanf("%lf%lf",&p3[i].x,&p3[i].y);
    Graham(p1,n1);
    Graham(p2,n2);
    Graham(p3,n3);
    Minkowski(p1,n1,p2,n2,p);
    int tot=cnt;
    Graham(p,tot);
    Minkowski(p,tot,p3,n3,F);
    Graham(F,cnt);
    int T;
    scanf("%d",&T);
    while(T--){
        Point t;
        scanf("%lf%lf",&t.x,&t.y);
        if(in(F,cnt,t*3.0))
           printf("YES
");
        else 
           printf("NO
");
    }
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wyy11/p/13069734.html