AOJ 1298 - Separate Points

ミナリンスキー和．

解法

n>=mとして一般性を失わない．(必要なのは白か黒かという区別だけである．)
(1) n=1のとき
m=1である．点は重ならないといっているので，適当な直線で分けられる．

(2) n=2のとき
m=1ならば，黒の2頂点を結ぶ線分内に白い点が入っていないときのみ，分けることができる．
m=2ならば，白黒それぞれの2頂点を結ぶ線分が交点をもたないときのみ，分けることができる．

(3) n>=3のとき
黒い点の凸包を求め，白い点がその凸包に含まれているかどうか調べる．
1点でも含まれていれば，分けることはできない．
同様に白い点に対して，凸包をとり，黒い点がそれに含まれているか調べる．

コード

ライブラリ部分は省略しています．

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

int N, M;
std::vector<P> bs, ws;

int main(){
    while(scanf("%d %d", &N, &M), N || M){
        bs.resize(N);
        ws.resize(M);
        
        for(int i=0;i<N;i++){
            ll x, y;
            scanf("%lld %lld", &x, &y);

            bs[i].real(x);
            bs[i].imag(y);
        }
        for(int i=0;i<M;i++){
            ll x, y;
            scanf("%lld %lld", &x, &y);

            ws[i].real(x);
            ws[i].imag(y);        
        }

        if(N == 1 && M == 1){
            puts("YES");
            continue;
        }

        if(N < M){std::swap(bs, ws); std::swap(N, M);}

        if(N == 2){
            if(M == 1){
                puts(ccw(bs[0], bs[1], ws[0]) ? "YES" : "NO");
                continue;
            }else{
                puts(!areIntersectedLines(bs[0], bs[1], ws[0], ws[1]) ? "YES" : "NO");
                continue;
            }
        }
        
        std::vector<P> ch = convex_hull(bs);

        bool res = true;
        for(int i=0;i<M;i++){
            if(isIn(ws[i], ch)){res = false; break;}
        }

        if(M >= 3){
            ch = convex_hull(ws);

            for(int i=0;i<N;i++){
                if(isIn(bs[i], ch)){res = false; break;}
            }
        }

        puts(res ? "YES" : "NO");
    }
}