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; }