けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 010 C - 浮気調査 (試験管茶色)

読解がちょっと大変......今の時代の問題文の方がわかりやすいね。

問題概要

高橋君は最高速度  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");
}