AOJ : 1298 - Separate Points
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1298
問題文中の図のように, 白点と黒点の位置が与えられる.
黒点と白点の集合を完全に分断するような直線が引けるかどうかを判定する問題.
プログラム
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; }