闵可夫斯基和例题题解

· · 题解

这是一道计算几何题。

对于像本蒟蒻这种计算几何没做过几道题的来说实在是太要命了（虽然只花了几个小时）

前置知识：凸包，向量

吐槽环节（可以跳过）

我觉得第一篇题解某个地方有点点小问题：

if(a*A[1]>0||A[tot]*a>0) return 0;

这里 A_1 已经是 (0,0) 了，所以叉积一定为 0 。

这不是关键，关键在于评论中说到：关于点是否在凸包内这东西弄错了！

比如像这种情况。

叉积为 0，但是点确实不在凸包内。

好了好了。

进入正题

啥是闵可夫斯基和呢？

给定两个点集 A,B

则它们的闵可夫斯基和为 C=A+B=\{a+b|a\in A,b\in B\}

这里定义两个点的加法为他们的横坐标、纵坐标分别相加。

那么闵可夫斯基和集合的点的数量级是 O(n^2) 的。

读者：您在逗我吗？您想让我 n^2 过十万吗？

那当然不，我们要的是闵可夫斯基和做完之后得到的点集的凸包，毕竟这玩意儿才有用。

给些图（假设三角形最上面的那个点的坐标是 (0,0)）

得到的就是

观察一下构成凸包的边。

我们发现，绿边经过平移可以构成原来的四边形，橙边经过平移可以构成原来的三角形。

再观察一下，可以发现闵可夫斯基和的凸包的边数是两个凸包的边数和，可以用归并排序之类的算法求出。

这一题中，考虑求出边界设移动向量 w 之后存在 b+w=a，其中 a\in A,b\in B

移项变成 w=a-b

于是我们就要构造一个闵可夫斯基和凸包。

等等， -b 怎么弄啊。

读入时把坐标取个反就可以了。

然后别的就没了。

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 300010 
using namespace std;
struct point{
    double x,y;
    void read(){scanf("%lf%lf",&x,&y);}
    void write(){printf("%lf,%lf ",x,y);}
}a[N],b[N],s1[N],s2[N],s[N],k,O,q;
struct my_stack{
    int t[N],len;
    void push(int x){t[len++]=x;}
    int operator [](int w){return t[len-w];}
    void pop(){len--;}
    void clear(){t[len=0]=0;}
}t;
point operator +(point a,point b)
{return (point){a.x+b.x,a.y+b.y};}
point operator -(point a,point b)
{return (point){a.x-b.x,a.y-b.y};}
double operator *(point a,point b)
{return a.x*b.y-a.y*b.x;}
bool operator ==(point a,point b)
{return a.x==b.x&&a.y==b.y;}
point operator ~(point a){return (point){-a.x,-a.y};}
double sqr(double a){return a*a;}
double calc(point a,point b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
bool cmp(point a,point b)
{
    double x=(a-k)*(b-k);
    if(x==0) return calc(a,k)<calc(b,k);
    else return x>0;
}
bool cmp2(point a,point b)
{
    double x=a*b;
    if(x==0) return calc(a,O)<calc(b,O);
    else return x>0;
}
double ans;
void convex(point*p,int&n)
{
    int w=1;
    for(int i=1;i<=n;i++)
        if(p[i].y<p[w].y||(p[i].y==p[w].y&&p[i].x<p[w].x)) w=i;
    swap(p[1],p[w]);k=p[1];
    sort(p+2,p+n+1,cmp);
    t.clear();
    t.push(1),t.push(2);
    for(int i=3;i<=n;i++)
    {
        while(t.len>1&&(p[i]-p[t[2]])*(p[t[1]]-p[t[2]])>=0) t.pop();
        t.push(i);
    }
    n=t.len;
    for(int i=1;i<=n;i++) p[i]=p[t.t[i-1]];
}
int n,m,cnt,T;
void minkowski()
{
    int i,j;
    for(i=1;i<n;i++) s1[i]=a[i+1]-a[i];
    for(i=1;i<m;i++) s2[i]=b[i+1]-b[i];
    s2[m]=b[1]-b[m];s1[n]=a[1]-a[n];
    i=1,j=1;
    s[cnt=1]=a[1]+b[1];
    while(i<=n&&j<=m)
    {
        if(s1[i]*s2[j]>0) s[cnt+1]=s[cnt]+s1[i++];
        else s[cnt+1]=s[cnt]+s2[j++];
        cnt++;
    }
    while(i<=n) s[cnt+1]=s[cnt]+s1[i++],cnt++;
    while(j<=m) s[cnt+1]=s[cnt]+s2[j++],cnt++;
}
bool query(point x)
{
    if(x*s[2]>0||s[cnt]*x>0||(x*s[2]==0&&calc(x,O)>calc(s[2],O))
        ||(x*s[cnt]==0&&calc(x,O)>calc(s[cnt],O))) return 1;
    int w=lower_bound(s+2,s+cnt+1,x,cmp2)-s-1;
    return (x-s[w])*(s[w+1]-s[w])>0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++) a[i].read();
    for(int i=1;i<=m;i++) b[i].read(),b[i]=O-b[i];
    convex(a,n),convex(b,m);
    minkowski(),convex(s,cnt);
    k=s[1]; for(int i=1;i<=cnt;i++) s[i]=s[i]-k;
    while(T--)
    {
        q.read();
        printf("%d\n",!query(q-k));
    }
}