AOJ : 1298 - Separate Points

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1298
問題文中の図のように, 白点と黒点の位置が与えられる.
黒点と白点の集合を完全に分断するような直線が引けるかどうかを判定する問題.

アルゴリズム

白点と黒点, それぞれ凸包により多角形に直す.
この2つの多角形が交差 or 内包の関係であればNO, そうでなければYES.

プログラム

const double EPS = 1e-8;
typedef complex<double> P;

//点集合に凸包を適用する
vector<P> convex_hull(vector<P> ps) {省略}

//多角形が点pを含むかの判定
int convex_contains(vector<P> ps,P p) {省略}

int main(void){
  int n,m;

  while(cin>>n>>m,n||m){
    vector<P> a(n);
    for(int i=0;i<n;i++) cin>>a[i].real()>>a[i].imag();
    vector<P> b(m);
    for(int i=0;i<m;i++) cin>>b[i].real()>>b[i].imag();

    a = convex_hull(a); //凸包適用
    b = convex_hull(b); //凸包適用

    bool flg = true;

    if(a.size() == 2 && b.size() == 2){
      flg = !intersectSS(a[0],a[1],b[0],b[1]);
    }
    else if(a.size() == 1 && b.size() == 2){
      flg = !intersectSP(b[0],b[1],a[0]);
    }
    else if(a.size() == 2 && b.size() == 1){
      flg = !intersectSP(a[0],a[1],b[0]);
    }

    if(b.size() >= 3){
      for(int i=0;i<n;i++){
        if(convex_contains(b,a[i])){
          flg = false;
          break;
        }
      }
    }
    if(a.size() >= 3){
      for(int i=0;flg && i<m;i++){
        if(convex_contains(a,b[i])){
          flg = false;
          break;
        }
      }
    }

    cout<<(flg?"YES":"NO")<<endl;
  }

  return 0;
}