AOJ 1298

なんか今日はAOJのサーバーが落ちているのでかわりにLiveArchiveに登録してそこで通しておきました。テストケース数がおおいらしい。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<complex>
#include<vector>
#include<stdlib.h>
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
typedef P point;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}
vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<point> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}
enum { OUT, ON, IN };
int contains(const vector<point>& P, const point& p) {
  bool in = false;
  for (int i = 0; i < P.size(); ++i) {
    point a = curr(P,i) - p, b = next(P,i) - p;
    if (imag(a) > imag(b)) swap(a, b);
    if (imag(a) <= 0 && 0 < imag(b))
      if (cross(a, b) < 0) in = !in;
    if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
  }
  return in ? IN : OUT;
}
bool intersectSS(const L &s, const L &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
int x[200];
int y[200];
P wolf[200];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
		for(int i=0;i<b;i++)scanf("%d%d",x+a+i,y+a+i);
		bool ok=true;
		int n=a+b;
		for(int i=0;i<n;i++)wolf[i]=P(x[i],y[i]);
		vector<point>A;
		vector<point>B;
		for(int i=0;i<a;i++)A.push_back(wolf[i]);
		for(int i=0;i<b;i++)B.push_back(wolf[a+i]);
		A=convex_hull(A);
		B=convex_hull(B);
		if(contains(A,B[0]))ok=false;
		if(contains(B,A[0]))ok=false;
		for(int i=0;i<A.size();i++)
			for(int j=0;j<B.size();j++)
				if(intersectSS(L(curr(A,i),next(A,i)),L(curr(B,j),next(B,j))))ok=false;
		if(ok)printf("YES\n");
		else printf("NO\n");
	}
}