POJ 1912 - A highway and the seven dwarfs

http://poj.org/problem?id=1912

概要

N 個の平面上の点が与えられる．

M 本の与えられた各直線に対して，N 個すべての点がその直線の片側にあるかどうかを答える．

制約

解法

愚直にやると O(N * M)．問題文中で M に制約が無いが，CEOI 2002, Košice, Slovakia の入力データを見てみると最大ケースで M = 100000 なので余裕で TLE する．

まず，N 個の点のうち，凸包となる点のみを考えればよいことがわかる． 凸包はソートした後に O(N) で求められるので，O(N log N) で計算できる．

与えられた直線の傾きを d とすると，傾きが d な直線を +y 方向から凸包に近づけたときに最初に交わる頂点 p1 と，逆に -y 方向から凸包に近づけたときの頂点 p2 がある． この p1, p2 を求めることができれば，直線に対して p1, p2 が片側にあるかどうかを調べるだけでよい．

凸包の上側をなす辺の傾きを右から順に d1[1], ..., d1[K1] とすると，d1 は昇順に並ぶ． この d1 に昇順を保つように d を挿入する位置の点が p1 である． 同様に凸包の下側をなす辺の傾きを左から順に d2[1], ..., d2[K2] として，これに d を挿入する位置の点が p2． これは二分探索により O(log N) で計算できるため，全体で O(N log N + M log N) となる．

 1 #include <cstdio>
 2 #include <complex>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef complex<double> P;
 6 static const double EPS = 1e-6;
 7 namespace std {
 8   bool operator<(const P& p, const P& q)
 9   {
10     return abs(p.real() - q.real()) < EPS ? p.imag() < q.imag() : p.real() < q.real();
11   }
12 };
13 
14 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
15 
16 int main()
17 {
18   int N;
19   scanf("%d", &N);
20   static P hs[100000];
21   for (int i = 0; i < N; i++) {
22     double x, y;
23     scanf("%lf %lf", &x, &y);
24     hs[i] = P(x, y);
25   }
26   sort(hs, hs+N);
27   static P ls[100000], us[100000];
28   int K1 = 0;
29   for (int i = 0; i < N; i++) {
30     while (K1 >= 2 && cross(ls[K1-2]-hs[i], ls[K1-1]-hs[i]) <= 0) {
31       K1--;
32     }
33     ls[K1++] = hs[i];
34   }
35   int K2 = 0;
36   us[K2++] = ls[K1-1];
37   for (int i = N-2; i >= 0; i--) {
38     while (K2 >= 2 && cross(us[K2-2]-hs[i], us[K2-1]-hs[i]) <= 0) {
39       K2--;
40     }
41     us[K2++] = hs[i];
42   }
43 
44   static double d1[100000], d2[100000];
45   for (int i = 0; i < K1-1; i++) {
46     const P d = ls[i+1] - ls[i];
47     d1[i] = d.imag()/d.real();
48   }
49   for (int i = 0; i < K2-1; i++) {
50     const P d = us[i+1] - us[i];
51     d2[i] = d.imag()/d.real();
52   }
53   double x1, y1, x2, y2;
54   while (scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2) != EOF) {
55     const double d = (y2-y1)/(x2-x1);
56     const int i = lower_bound(d1, d1+K1-1, d) - d1;
57     const int j = lower_bound(d2, d2+K2-1, d) - d2;
58     const P p(x1, y1), q(x2, y2);
59     if (cross(ls[i]-p, q-p) * cross(us[j]-p, q-p) < 0) {
60       puts("BAD");
61     } else {
62       puts("GOOD");
63     }
64   }
65   return 0;
66 }
poj/1912.cc