AOJ 0204 - UFO Shooting Down Operation

わーとおったよー．*1
結局最後は線分と点の計算が間違っていたみたい．
すべて参考にした方のおかげといってもいいです．ありがとうございます．
参考: AOJ : 0204 - UFO撃墜作戦 (UFO Shooting Down Operation) - Respect2Dの日記, Public Solutionsにあったnatrium11321さんのコード

以下3点をする．

あきらめる

あるUFOについてLazer砲からの距離(d)が安全圏の半径(R)以下のとき，断念する．

撃つ

最も近いUFOを求め，Lazerを撃つ．Lazerとの距離(線分と点の距離)がUFOの半径以下であれば道連れとなる．

UFOの移動

UFOの位置から単位ベクトルを求める．それに-v(vはUFOの速度)を掛ける．これが変位となる．そして，足すだけ．

注意したいこと

Lazerとの距離がUFOの半径以下でも，Lazerの方向と対にあるUFOは落とせない
Lazerは距離がR以下でかすっても効力を持たないこと．(推測)
無理して解かない(重要)
解けないときはテストケースをつくり，先人さんのコードの出力と自分の出力を見比べるのがよかったです．

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

struct P{
	double x, y;
	P operator+(const P p) const;
	P operator-(const P p) const;
};

P operator*(const double k, const P p){return {k * p.x, k * p.y};}
P P::operator+(const P p) const{return {x+p.x, y+p.y};}
P P::operator-(const P p) const{return {x-p.x, y-p.y};}

typedef P Vector;

const P ORIGIN_P = {0, 0};
const double EPS = 1e-10;

double abs(double d){
	return (d>0)?d:-d;
}

double abs(P p){
	return sqrt(p.x*p.x + p.y*p.y);
}

double dotProduct(Vector v1, Vector v2){return v1.x*v2.x + v1.y*v2.y;}
double crossProduct(Vector v1, Vector v2){return v1.x*v2.y - v1.y*v2.x;}

Vector createUnitVector(Vector v){
	double dist = abs(v);
	if(dist < EPS){
		return {0, 0};
	}
	return (1/dist) * v;
}

//直線ab上に点cはあるか
bool is_point_on_line(P a, P b, P c){
	return (crossProduct(b-a, c-a) < EPS &&
					dotProduct(b-a, c-a) > -EPS &&
					dotProduct(a-b, c-b) > -EPS);
}

//直線abと点P間の距離
double distance_line_p(P a, P b, P p){
	if(dotProduct(b-a, p-a) < EPS)return abs(p-a);
	if(dotProduct(a-b, p-b) < EPS)return abs(p-b);
	return abs(crossProduct(a-b, p-a)) / abs(a-b);
}
 
class UFO{
public:
	P p;
	double r, v;
	Vector unit_v;
	UFO(P _p, double _r, double _v);
};

UFO::UFO(P _p, double _r, double _v)
	:p(_p), r(_r), v(_v){
	unit_v = createUnitVector(p);
}

double R;
int n;

bool comp(const UFO& l_ufo, const UFO& r_ufo){
	return abs(l_ufo.p) < abs(r_ufo.p);
}

void shoot(std::vector<UFO> &uv){//最も近いUFOの中心に向けてLazerを発射する
	std::sort(uv.begin(), uv.end(), comp);
 
	UFO attacked_u = uv[0];
	
	for(int i=0;i<uv.size();i++){
		UFO u = uv[i];
		double dist = distance_line_p(R * attacked_u.unit_v, 100000 * attacked_u.unit_v, u.p);

		if(dist < u.r + EPS){//破壊
			uv.erase(uv.begin() + i);
			i--;
		}
	}
}

void moveUFO(std::vector<UFO> &uv){//UFOの移動
	std::sort(uv.begin(), uv.end(), comp);

	int uv_size = uv.size();
	for(int i=0;i<uv_size;i++){
		UFO &u = uv[i];
		if(abs(u.p) > abs(-u.v * u.unit_v)){
			u.p = u.p - u.v * u.unit_v;
		}else{
			u.p = {0, 0};
		}
	}
}
int countUFO(std::vector<UFO> &uv){//生存確定したUFOの数を返す
	std::sort(uv.begin(), uv.end(), comp);

	int res = 0;
	for(int i=0;i<uv.size();i++){
		if(abs(uv[i].p) < R + EPS){
			uv.erase(uv.begin() + i);
			i--;
			res++;
		}

	}
	return res;
}

int main(){
	while(std::cin >> R >> n, n){
		std::vector<UFO> uv;
		for(int i=0;i<n;i++){
			P p;
			double r, v;
			std::cin >> p.x >> p.y >> r >> v;
			UFO u(p, r, v);
			uv.push_back(u);
		}

		std::sort(uv.begin(), uv.end(), comp);

		int res = 0;//生き残ったUFO
		while(!uv.empty()){
			moveUFO(uv);
			res += countUFO(uv);
			shoot(uv);
		}

		std::cout << res << std::endl;
	}
}

*1:わーいわーい