全体公開 > 合同練習会 > 20130323 > F 頑固なヌーRick

問題の概要

Rickたちヌーの群れが, ある方角FSを目指している.
FSに向かうにあたり, いくつかの餌場があり, それらを直線でつないだ経路で進む.
経路の隣合う餌場は, 距離がd以下でなければならない.
また, 餌場では90度より向きを変えてはならない.
更に, 常にFSの方角から90度以下を向いていなければならない.
これらの条件を満たす餌場のうち, 変える向きが最小な所に向かう.
この時, Rickたちはどのように動くだろうか.

実装の方針, 注意点

...

(符号無し)角度の大小 <=> cosの大小の逆
であり, 90度との比較は正負でわかる為, cos で処理する.
また, 念の為, 比較は小さい正数EPSを噛ませて行った.

ソースコード

...

typedef complex<double> P;
#define X real()
#define Y imag()
double dot(P a, P b){
    return (a * conj(b)).X;
}
double dist(P a, P b){
    return abs(a - b);
}
double costheta(P a, P b){
    a /= abs(a);
    b /= abs(b);
    return dot(a, b);
}
bool solve(){
    P fs;
    cin >> fs.X >> fs.Y;
    int n; cin >> n;
    int s; cin >> s;
    double d; cin >> d;
    if(!n) return false;
 
    vector<P> in(n);
    rep(i, n) cin >> in[i].X >> in[i].Y;
 
    --s;
    P dir = fs;
 
    vector<int> res(1, s);
    while(true){
        pair<double, int> nex(-INF, -1);
        rep(i, n) if(i != s) if(dist(in[s], in[i])-EPS < d){
            if(costheta(dir, in[i]-in[s]) < EPS) continue;
            double c = costheta(in[i]-in[s], fs);
            if(c < EPS) continue;
            maxeq(nex, make_pair(c, i));
        }
        if(nex.snd == -1) break;
        int t = nex.snd;
        dir = in[nex.snd] - in[s];
        s = nex.snd;
        res.pb(s);
    }
    repsz(i, res){
        if(i) cout << " ";
        cout << res[i]+1;
    }
    cout << endl;
    return true;
}
 

編集

---