問題概要

高橋君は最高速度 $V$ で移動することができる。

高橋君は時刻 $0$ に地点 $(s_{x}, s_{y})$ を出発し、時刻 $T$ に地点 $(t_{x}, t_{y})$ に到達しました。

その過程で $N$ 個の地点 $(x_{1}, y_{1})$ , $\dots$ , $(x_{N}, y_{N})$ のいずれかに寄り道した可能性が示唆されている。そのよなことが移動速度の観点から可能かどうかを判定せよ。

制約

$1 \le N \le 1000$

考えたこと

各 $i$ に対して、 $(s_{x}, s_{y})$ から $(x_{i}, y_{i})$ への移動距離と $(x_{i}, y_{i})$ から $(t_{x}, t_{y})$ への移動距離の合計値を求めていきましょう。

そのうちの最小値を速度 $V$ で移動したときに、 $T$ 秒以内におさまれば可能です。

計算量は $O(N)$ となります。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    double sx, sy, tx, ty, T, V;
    cin >> sx >> sy >> tx >> ty >> T >> V;
    int N;
    cin >> N;

    double Min = 1LL<<60;
    for (int i = 0; i < N; ++i) {
        double X, Y;
        cin >> X >> Y;
        double tmp1 = sqrt( (X - sx) * (X - sx) + (Y - sy) * (Y - sy) );
        double tmp2 = sqrt( (X - tx) * (X - tx) + (Y - ty) * (Y - ty) );
        Min = min(Min, tmp1 + tmp2);
    }
    if (Min <= T * V) puts("YES");
    else puts("NO");
}