AOJ 1298 - Separate Points

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1298

概要

二次元座標上に n 個の白い点の位置と m 個の黒い点の位置が与えられるので，白い点と黒い点を左右に分けるような直線を引けるかどうか答える．

直線上に白い点と黒い点の両方があった場合，その直線は題意を満たさない．

制約

解法

同じ色の2点を結ぶような直線を全通り試した．O( (n+m)^3 ) で厳しいものの，一応 03:02 で通った．

ただしこれには「すべての点が一直線上に並んでいるとき」というエッジケースが存在する． サンプルにあったので気付けた． このときは x 方向，y 方向それぞれに関して白と黒がちゃんと分かれているかチェックすればいい．

  1 #include <iostream>
  2 #include <vector>
  3 #include <complex>
  4 using namespace std;
  5 typedef complex<long long> P;
  6 
  7 inline P::value_type cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
  8 
  9 bool ok(const vector<P>& ps, int N, int i1, int i2)
 10 {
 11   const int NM = ps.size();
 12   const int color = i1 < N;
 13   int cnt[2][2] = {{0, 0}, {0, 0}};
 14   for (int i = 0; i < NM; i++) {
 15     const long long c = cross(ps[i2] - ps[i1], ps[i] - ps[i1]);
 16     const int col = i < N;
 17     if (c == 0) {
 18       if (color != col) {
 19         return false;
 20       }
 21     } else {
 22       ++cnt[col][c < 0];
 23     }
 24   }
 25   return (cnt[0][0] == 0 && cnt[1][1] == 0) || (cnt[0][1] == 0 && cnt[1][0] == 0);
 26 }
 27 
 28 bool check(const vector<P>& ps, int N)
 29 {
 30   for (int i = 0; i < N; i++) {
 31     for (int j = i+1; j < N; j++) {
 32       if (ok(ps, N, i, j)) {
 33         return true;
 34       }
 35     }
 36   }
 37   const int NM = ps.size();
 38   for (int i = N; i < NM; i++) {
 39     for (int j = i+1; j < NM; j++) {
 40       if (ok(ps, N, i, j)) {
 41         return true;
 42       }
 43     }
 44   }
 45   return false;
 46 }
 47 
 48 inline int cmp(long long x, long long y)
 49 {
 50   if (x == y) {
 51     return 0;
 52   } else if (x < y) {
 53     return -1;
 54   } else {
 55     return 1;
 56   }
 57 }
 58 
 59 bool check_edgecase(const vector<P>& ps, const int N)
 60 {
 61   const int NM = ps.size();
 62   const int x = cmp(ps[0].real(), ps[N].real());
 63   for (int i = 0; i < N; i++) {
 64     for (int j = N; j < NM; j++) {
 65       if (x != cmp(ps[i].real(), ps[j].real())) {
 66         return false;
 67       }
 68     }
 69   }
 70   const int y = cmp(ps[0].imag(), ps[N].imag());
 71   for (int i = 0; i < N; i++) {
 72     for (int j = N; j < NM; j++) {
 73       if (y != cmp(ps[i].imag(), ps[j].imag())) {
 74         return false;
 75       }
 76     }
 77   }
 78   return true;
 79 }
 80 
 81 int main()
 82 {
 83   int N, M;
 84   while (cin >> N >> M && N != 0) {
 85     vector<P> ps(N+M);
 86     for (int i = 0; i < N+M; i++) {
 87       cin >> ps[i].real() >> ps[i].imag();
 88     }
 89 
 90     bool straight = true;
 91     if (N+M > 2) {
 92       const long long c0 = cross(ps[2]-ps[0], ps[1]-ps[0]);
 93       for (int i = 3; i < N+M; i++) {
 94         const long long c = cross(ps[i]-ps[0], ps[1]-ps[0]);
 95         if (c != c0) {
 96           straight = false;
 97           break;
 98         }
 99       }
100     }
101     if (straight) {
102       cout << (check_edgecase(ps, N) ? "YES" : "NO") << endl;
103     } else {
104       cout << (check(ps, N) ? "YES" : "NO") << endl;
105     }
106   }
107   return 0;
108 }
aoj/1298.cc