На игровой платформе VK Play опубликовали MOBA игр...

Question

На игровой платформе VK Play опубликовали MOBA игру с одноименной аббревиатурой в названии – Venetian Karatekas (Венецианские Каратисты). Сражения происходят на виртуальной арене, по атмосфере, архитектуре и ландшафту напоминающей Венецию[1]. Игроки управляют мастерами разных стилей каратэ и прочих боевых искусств. В списке умений, как правило, броски, пинки, тайные захваты и прочие приёмы.

В игре присутствует тайный магазин — Купец, который постоянно перемещается по ломанной траектории туда и обратно с единичной скоростью. Изначально, в момент времени 0, Купец находится в координатах первой точки ломанной траектории.
Чтобы купить предметы у этого Купца, игрокам необходимо добраться до него. В связи с этим, решили разработать дополнение для игры, которое выводит координаты Купца в нужный момент времени.

Ваша задача заключается в том, чтобы написать код, который умеет определять какие координаты Купца в заданный момент времени.

В первой строке задано
2
целых числа:
N
(
2
≤
N
≤
10
5
)
— количество точек ломанной, по которой бродит Купец, и
T
(
1
≤
T
≤
10
5
)
— количество запросов координат Купца в конкретный момент времени.

В следующих
N
строках, через пробел, записаны пары целых чисел
x
i
,
y
i
(
0
≤
x
i
,
y
i
≤
10
4
)
— координаты точек, которые задают ломанную.

В следующих
T
строках записано по одному целому числу
t
i
(
0
≤
t
i
≤
10
11
)
— запрашиваемый момент времени.

Выведите ровно
T
строк. В
i
-й строке, через пробел, выведите пару чисел — координаты Купца в момент времени
t
i
.

Координаты следует выводить с абсолютной или относительной ошибкой не более чем
10
−
4
.

Answer 1

Ниже — быстрый и точный алгоритм: считаем длины отрезков ломаной и их префиксы. Полный путь «туда-обратно» имеет период $2L$ , где $L$ — длина пути от первой точки до последней. Для момента времени $t$ берём $d=t\bmod 2L$ . Если $d\le L$ , идём вперёд, иначе берём зеркальное расстояние $s=2L-d$ и берём точку на прямом пути на расстоянии $s$ от начала. Дальше бинарным поиском находим нужный отрезок и линейно интерполируем координаты.

C++17 (O(N + T log N), точность ≤ 1e-4)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, T;
    if (!(cin >> N >> T)) return 0;

    vector<long double> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];

    // Длины отрезков и префиксы по отрезкам
    int M = N - 1;
    vector<long double> seg_len(M), pref(M + 1, 0.0L);
    for (int i = 0; i < M; ++i) {
        long double dx = x[i + 1] - x[i];
        long double dy = y[i + 1] - y[i];
        seg_len[i] = hypotl(dx, dy);
        pref[i + 1] = pref[i] + seg_len[i];
    }

    long double L = pref[M];

    cout.setf(std::ios::fixed); 
    cout << setprecision(10);

    // Если весь путь вырожден (все точки совпали)
    if (L == 0.0L) {
        for (int qi = 0; qi < T; ++qi) {
            long long t; cin >> t;
            cout << (double)x[0] << ' ' << (double)y[0] << '\n';
        }
        return 0;
    }

    long double period = 2.0L * L;

    for (int qi = 0; qi < T; ++qi) {
        long long t_int; 
        cin >> t_int;

        long double d = fmodl((long double)t_int, period);
        if (d < 0) d += period;               // на всякий случай

        long double s = (d <= L) ? d : (2.0L * L - d);  // расстояние по прямому пути
        // Чуть-чуть страхуемся от ошибок округления
        if (s < 0) s = 0;
        if (s > L) s = L;

        // Точка ровно в конце прямого пути
        if (fabsl(s - L) <= 1e-12L) {
            cout << (double)x[N - 1] << ' ' << (double)y[N - 1] << '\n';
            continue;
        }

        // Ищем отрезок: pref[i] <= s < pref[i+1]
        int j = int(upper_bound(pref.begin(), pref.end(), s) - pref.begin()) - 1;
        if (j < 0) j = 0;           // на всякий случай
        long double len = seg_len[j];

        long double alpha = (len == 0.0L) ? 0.0L : (s - pref[j]) / len; // 0..1
        long double X = x[j] + alpha * (x[j + 1] - x[j]);
        long double Y = y[j] + alpha * (y[j + 1] - y[j]);

        cout << (double)X << ' ' << (double)Y << '\n';
    }
    return 0;
}

Примечания:

Используется long double для устойчивости при больших суммах длин; вывод — с setprecision(10), что гарантирует ошибку ≤ 1e-4.
Обработка вырожденного случая $L=0$ : Купец всегда в первой точке.
Время на запрос: $O(\log N)$ (бинарный поиск по префиксам).

На игровой платформе VK Play опубликовали MOBA игр...

سؤال

سؤال

الفكرة

Clarifying polyline movement

Defining movement and reflection

Finalizing the polyline computation

Segment search and precision

Handling precision and segment search

الإجابة

C++17 (O(N + T log N), точность ≤ 1e-4)

مشاركة هذا السؤال والجواب