Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-19

PKU 3805 -- Separate Points

| 18:33 | PKU 3805 -- Separate Points - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3805 -- Separate Points - Wrong Answer -- japlj PKU 3805 -- Separate Points - Wrong Answer -- japlj のブックマークコメント

凸包とって全部の線を試す。一本の線の上に点がいくつもある場合を考えて ccw を多少いじる。


#include<cstdio>
#include<complex>
#include<algorithm>

using namespace std;

typedef complex<int> pt;
namespace std {
  bool operator < (const pt& a, const pt& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

int cross(const pt& a, const pt& b) {
  return imag(conj(a)*b);
}
int dot(const pt& a, const pt& b) {
  return real(conj(a)*b);
}
int ccw(pt a, pt b, pt c) {
  b -= a; c -= a;
  if(cross(b,c)>0) return 1; if(cross(b,c)<0) return -1;
  if(dot(b,c)<0) return 0; if(norm(b)<=norm(c)) return -2;
  return 0;
}

int convex_hull(pt *ps, int n)
{
  int k=0;
  pt ch[200];
  sort(ps, ps+n);
  for(int i=0; i<n; ch[k++]=ps[i++])
    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--])
    while(k>=t && ccw(ch[k-2],ch[k-1],ps[i])<=0) --k;
  for(int i=0; i<k-1; ++i) ps[i] = ch[i];
  return k-1;
}

int main()
{
  int n, m;
  while(scanf("%d%d", &n, &m), n||m) {
    pt p[200];
    for(int i=0; i<n+m; ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      p[i] = pt(x, y);
    }
    if(n>=3 && m>=3) {
      int N = n;
      n = convex_hull(p, n);
      for(int i=N; i<N+m; ++i) p[n+i-N] = p[i];
      m = convex_hull(p+n, m);
    }
    bool ok = false;
    for(int i=0; !ok&&i<n; ++i) {
      for(int j=n; !ok&&j<n+m; ++j) {
	int b[5]={0}, w[5]={0};
	for(int k=0; k<n; ++k) b[ccw(p[i],p[j],p[k])+2]++;
	for(int k=n; k<n+m; ++k) w[ccw(p[i],p[j],p[k])+2]++;
	ok = true;
	b[ccw(p[i],p[j],p[i])+2]--;
	for(int k=0; k<5; ++k) ok &= b[k]*w[k]==0;
	b[ccw(p[i],p[j],p[i])+2]++;
	w[ccw(p[i],p[j],p[j])+2]--;
	for(int k=0; k<5; ++k) ok &= b[k]*w[k]==0;
      }
    }
    puts(ok ? "YES" : "NO");
  }
  return 0;
}
 |