// 2009アジア地区予選 D : Separate Points #include #include #include #include #include using namespace std; const double EPS = 1e-8; typedef complex P; struct L { P p, q; L(P p, P q) : p(p), q(q) {} }; double dot(P a, P b){ return real(conj(a)*b); } double cross(P a, P b){ return imag(conj(a)*b); } double angle(P a, P b){ return arg(conj(a)*b); } bool compare(const P &a, const P &b){ return make_pair(real(a),imag(a)) < make_pair(real(b),imag(b)); } vector

convexHull(vector

vp){ if(vp.size() < 3) return vp; sort(vp.begin(), vp.end(), compare); vector< pair > vi; for(int i=1;i res(2); res[0] = vp[0]; res[1] = vp[vi[0].second]; for(int i=1;i=2&&cross(res[sz-1]-res[sz-2],next-res[sz-1]) vp, P p){ if(vp.size()==1) return false; bool in = false; for(int i=0;i imag(b)) swap(a,b); if(imag(a) < EPS && EPS < imag(b)) if(cross(a,b) < 0) in = !in; if(abs(cross(a,b)) a, vector

b){ if(a.size()!=1&&b.size()!=1) for(int i=0;i> n >> m, n){ int x, y; vector

black, white; for(int i=0;i> x >> y; black.push_back(P(x,y)); } for(int i=0;i> x >> y; white.push_back(P(x,y)); } cout << (separate(convexHull(black), convexHull(white)) ? "YES" : "NO") << endl; } }