题解：UVA10256 The Great Divide

· · 题解

定义对于两个点集 A,B，其闵可夫斯基和为 A+B=\{a+b,a\in A,b\in B\}。

我们研究两个凸包之间的闵可夫斯基和，可以发现是把凸包中的边进行了平移得到的，等价于对于两个凸包中的边进行极角排序之后放在一起。凸包本来就有单调性，所以可以直接归并这些边，复杂度是 O(|A|+|B|) 的。

具体做法就是初始点是 a_0+b_0，然后我们把凸包中的相邻点作差分（得到了边），按照斜率把种边进行归并加入，每次都在上一个点的基础上加上一个新加入的向量（边）得到一个新的点。注意求完 Minkowski 之后最好再求一次凸包，去掉一次多余的点，比如三点共线之类的。

本题等价于对于 A 和 (-B) 求闵可夫斯基和之后，判断给 (0,0) 是否在凸包之内。

按照上文所述求出凸包之后，我们任意选择一个点作为起点对于凸包进行三角剖分。也就是通过该起点和凸包中任意两个相邻点，把凸包划分为 n-2 个三角形。然后我们只需要通过叉积判断方向，二分出给定点如果被凸包包含，会在哪个三角形之内，然后再判断是否在这个三角形之内（直接用叉积对于第三条边判定即可）。注意 corner case 就是可能出现某个点恰好处于最后一条边上，特判一下即可。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
struct Point{
    int x,y;
    bool operator < (const Point &rhs) const { return x<rhs.x||(x==rhs.x&&y<rhs.y); }
}; typedef Point Vector; vector<Point> s,t,ps;
ll Cross (Vector v1,Vector v2){ return 1ll*v1.x*v2.y-1ll*v1.y*v2.x; }
Vector operator + (Vector v1,Vector v2){ return (Vector){v1.x+v2.x,v1.y+v2.y}; }
Vector operator - (Vector v1,Vector v2){ return (Vector){v1.x-v2.x,v1.y-v2.y}; }
int n,m,q; vector<Point> H;
vector<Point> Hull(vector<Point> S){
    int sz=S.size(); if(sz<=1) return S;
    sort(S.begin(),S.end()); int k=0,t; 
    H.clear(); H.resize(2*sz); 
    for(int i=0;i<sz;H[k++]=S[i++])
        while(k>1&&Cross(S[i]-H[k-1],H[k-1]-H[k-2])>=0) k--;
    for(int i=sz-2,t=k;i>=0;H[k++]=S[i--])
        while(k>t&&Cross(S[i]-H[k-1],H[k-1]-H[k-2])>=0) k--;
    H.resize(k-1); return H;
}
vector<Point> Minkowski(vector<Point> S,vector<Point> T){
    H.clear(); H.pb(S[0]+T[0]);
    int s1=S.size(),t1=T.size(); Point s0=S[0],t0=T[0];
    for(int i=0;i<s1-1;i++) S[i]=S[i+1]-S[i];
    for(int i=0;i<t1-1;i++) T[i]=T[i+1]-T[i];
    S[s1-1]=s0-S[s1-1]; T[t1-1]=t0-T[t1-1];
    for(int i=0,j=0;i<s1||j<t1;){
        if(i==s1) H.pb(H.back()+T[j++]);
        else if(j==t1) H.pb(H.back()+S[i++]);
        else if(Cross(S[i],T[j])>=0) H.pb(H.back()+S[i++]);
        else H.pb(H.back()+T[j++]);
    }
    return H;
}
bool chk(Point n0){
    int l=0,r=s.size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(Cross(s[mid]-s[0],n0-s[0])>=0) l=mid;
        else r=mid-1;
    }
    if(l==s.size()-1){
        if(Cross(n0-s[0],n0-s[l])==0&&s[0].x<=n0.x&&n0.x<=s[l].x&&s[0].y<=n0.y&&n0.y<=s[l].y)
            return 1;
        return 0;
    }
    if(Cross(s[l+1]-s[l],n0-s[l])>=0) return 1;
    else return 0;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>n>>m&&n&&m){
        s.clear(); t.clear();
        for(int i=1;i<=n;i++){
            int x,y; cin>>x>>y;
            s.pb((Point){x,y});
        }
        for(int i=1;i<=m;i++){
            int x,y; cin>>x>>y;
            t.pb((Point){-x,-y});
        }
        s=Hull(s); t=Hull(t);
        s=Minkowski(s,t); s=Hull(s);
        if(chk((Point){0,0})) cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}