AOJ : 0204 - UFO撃墜作戦 (UFO Shooting Down Operation)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0204
日本語の問題文があるので省略

アルゴリズム

1分ごとにUFOを動かして、シミュレートしました。
この問題において、一番注意しなければいけないのは、発射したレーザーがどのUFOに命中するかどうかの判定です。
問題文にあるように、レーザーは「UFOにかする」だけで命中したことになります。
そのため、レーザーが命中するかどうかの判定文は次のようになります。

「原点から、レーザーの標的とするUFOの中心座標の方向へ、無限に伸ばした線分」と「UFO X」の中心座標との距離が、「UFO X」の半径以下であるならば、命中する。ただし、原点から半径Rの範囲は、レーザーの有効範囲外であるため、当たったことにはならない。

なんていうか、文章で説明しづらいです。

プログラム

#include <iostream>
#include <complex>
#include <vector>
using namespace std;

typedef complex<double> P;

#define INF 999999999
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

//内積
double dot(P a, P b){
  return (a.real() * b.real() + a.imag() * b.imag());
}

//外積
double cross(P a,P b){
  return (a.real() * b.imag() - a.imag() * b.real());
}

//線分abと点cの距離
double distance_ls_p(P a, P b, P c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

//線分ab上に点cがあるか
int is_point_on_line(P a, P b, P c) {
  return EQ( cross(b-a, c-a), 0.0 ) &&
         (dot(b-a, c-a) > -EPS) &&
         (dot(a-b, c-b) > -EPS);
}

//pの移動後の位置を求める
P move(P p,double v){
  P b = -p / abs(-p); //-p の単位ベクトル
  return p + b * v;
}

int main(void){
  int n;
  double R;

  while(cin>>R>>n && (R||n)){
    int ans = 0;
    vector<P> p(n);
    vector<double> r(n),v(n);

    for(int i=0;i<n;i++){
      cin>>p[i].real()>>p[i].imag()>>r[i]>>v[i];
    }

    while(p.size() != 0){
      int minIdx = -1;
      double minDist = INF;

      for(int i=0;i<p.size();i++){
        //ビームがあたらない場所ならカウント
        if(abs(p[i]) < R + EPS){
          ans++;
          p.erase(p.begin()+i);
          r.erase(r.begin()+i);
          v.erase(v.begin()+i);
          i--;
          continue;
        }

        P aft = move(p[i],v[i]);
        double dist = abs(aft);

        //(0,0)を通過してしまうか,半径Rの範囲内ならカウント
        if(is_point_on_line(p[i],aft,P(0,0)) || dist < R + EPS){
          ans++;
          p.erase(p.begin()+i);
          r.erase(r.begin()+i);
          v.erase(v.begin()+i);
          i--;
          continue;
        }

        p[i] = aft;
        if(minDist > dist){
          minIdx = i;
          minDist = dist;
        }
      }

      if(minIdx == -1) break;

      P pp = p[minIdx];
      for(int i=0;i<p.size();i++){
        P b = pp / abs(pp); //ppの単位ベクトル
        P o = b * R + b * EPS;
        //原点からR離れた場所を始点として,pp方向へ長く伸びる線分と p[i] の距離が r[i] 以下ならあたる
        if(distance_ls_p(o,b*10000000.0,p[i]) < r[i] + EPS){
          p.erase(p.begin()+i);
          r.erase(r.begin()+i);
          v.erase(v.begin()+i);
          i--;
        }
      }
    }

    cout<<ans<<endl;
  }

  return 0;
}