POJ 3774 - Elune's Arrow

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

概要

\((x_0, y_0)\) の位置から \((\mathit{dx}, \mathit{dy})\) の方向にビームを撃つ。 \(n\) 体の敵がおり、敵は凸な多角形として表現されている。 2番目から \(n\) 番目までの敵に邪魔されることなく1番目の敵にビームが当たるかどうか答える。

制約

解法

まず \((x_0, y_0)\) からの半直線上に1番目の敵がいるかどうか調べる。 いる場合、その半直線と多角形の交点を求め、その交点と \((x_0, y_0)\) を結ぶ線分が他の敵と交わらないかどうか調べる。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <complex>
  4 #include <cmath>
  5 using namespace std;
  6 typedef complex<double> P;
  7 static const double EPS = 1e-6;
  8 
  9 inline double dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }
 10 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 11 
 12 int ccw(const P& a, P b, P c)/*{{{*/
 13 {
 14   b -= a;
 15   c -= a;
 16   if (cross(b, c) > EPS) {
 17     return +1;
 18   } else if (cross(b, c) < -EPS) {
 19     return -1;
 20   } else if (dot(b, c) < -EPS) {
 21     return +2;
 22   } else if (dot(b, b) + EPS < dot(c, c)) {
 23     return -2;
 24   } else {
 25     return 0;
 26   }
 27 }/*}}}*/
 28 
 29 struct segment/*{{{*/
 30 {
 31   P a, b;
 32   segment() {}
 33   segment(const P& x, const P& y) : a(x), b(y) {}
 34 
 35   // AOJ 2402 Milkey Way
 36   inline bool intersects(const segment& seg) const
 37   {
 38     return ccw(a, b, seg.a) * ccw(a, b, seg.b) <= 0
 39       && ccw(seg.a, seg.b, a) * ccw(seg.a, seg.b, b) <= 0;
 40   }
 41 
 42   inline P intersection(const segment& seg) const
 43   {
 44     // assert(intersects(seg))
 45     const P x = b - a;
 46     const P y = seg.b - seg.a;
 47     return a + x*(cross(y, seg.a - a))/cross(y, x);
 48   }
 49 
 50 };/*}}}*/
 51 
 52 struct polygon/*{{{*/
 53 {
 54   vector<P> ps;
 55   polygon() {}
 56   polygon(const vector<P>& v) : ps(v) {}
 57 
 58   inline int size() const { return ps.size(); }
 59   inline void push_back(const P& p) { ps.push_back(p); }
 60   inline P& operator[](int i) { return ps[i]; }
 61   inline const P& operator[](int i) const { return ps[i]; }
 62 
 63   bool intersects(const segment& seg) const
 64   {
 65     const int N = size();
 66     for (int i = 0; i < N; i++) {
 67       if (seg.intersects(segment(ps[i], ps[(i+1)%N]))) {
 68         return true;
 69       }
 70     }
 71     return false;
 72   }
 73 
 74   P intersection_halfline(const segment& seg) const
 75   {
 76     // assert(intersects(seg));
 77     const int N = size();
 78     double len = 1e10;
 79     P p;
 80     for (int i = 0; i < N; i++) {
 81       const segment side(ps[i], ps[(i+1)%N]);
 82       if (seg.intersects(side)) {
 83         const P tmp = seg.intersection(side);
 84         const double d = abs(seg.a - tmp);
 85         if (d < len) {
 86           len = d;
 87           p = tmp;
 88         }
 89       }
 90     }
 91     return p;
 92   }
 93 };/*}}}*/
 94 
 95 P read()
 96 {
 97   int x, y;
 98   scanf("%d %d", &x, &y);
 99   return P(x, y);
100 }
101 
102 bool hits(const P& o, const P& dir, const vector<polygon>& v)
103 {
104   const int N = v.size();
105   const polygon target = v[0];
106   const segment half(o,  o + (dir/abs(dir))*1e7);
107   if (!target.intersects(half)) {
108     return false;
109   }
110   const segment seg(o, target.intersection_halfline(half));
111 
112   for (int i = 1; i < N; i++) {
113     if (v[i].intersects(seg)) {
114       return false;
115     }
116   }
117   return true;
118 }
119 
120 int main()
121 {
122   int N;
123   while (scanf("%d", &N) != EOF && N != 0) {
124     const P o = read();
125     const P dir = read();
126     vector<polygon> v;
127     for (int i = 0; i < N; i++) {
128       polygon p;
129       int M;
130       scanf("%d", &M);
131       for (int j = 0; j < M; j++) {
132         p.push_back(read());
133       }
134       v.push_back(p);
135     }
136     puts(hits(o, dir, v) ? "HIT" : "MISS");
137   }
138   return 0;
139 }
poj/3774.cc