题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Geometry{
    struct vec{
        int x, y;
        vec() = default;
        vec(int x, int y): x(x), y(y) {}
        vec operator+(const vec &rhs) const { return {x + rhs.x, y + rhs.y}; }
        vec operator-(const vec &rhs) const { return {x - rhs.x, y - rhs.y}; }
        // not for value compare
        bool operator<(const vec &rhs) const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        long double len() { return sqrt(x * x + y * y); }
    };
    inline int dot(vec a, vec b) { return a.x * b.x + a.y * b.y; }
    inline int cross(vec a, vec b) { return a.x * b.y - a.y * b.x; }
    inline int quadrant(vec a) { return (a.y < 0) << 1 | ((a.x < 0) ^ (a.y < 0)); }
    inline bool clockwise_cmp(vec a, vec b){
        if(quadrant(a) != quadrant(b)){
            return quadrant(a) > quadrant(b);
        }
        return cross(a, b) == 0 ? a.len() > b.len() : cross(a, b) < 0;
    }
} // namespace Geometry
namespace Main{
    const int N = 505;
    using namespace Geometry;
    int t, n, m, lst_id[N][N];
    vec p[N];
    long double lst_l[N][N];
    vector<vec> cent[N];
    map<vec, int> id;
    void Main(){
        input(t);
        while(t--){
            id.clear();
            input(n, m);
            for(int i = 1; i <= n; i++) input(p[i].x, p[i].y), id[p[i]] = i;
            cent[0].assign(p + 1, p + n + 1);
            for(int i = 1; i <= n; i++){
                cent[i].clear();
                for(int j = 1; j <= n; j++) if(i != j) cent[i].push_back(p[j]);
                sort(cent[i].begin(), cent[i].end(), [&](vec a, vec b){
                    return clockwise_cmp(a - p[i], b - p[i]);
                });
            }
            while(m--){
                vec s, dir; long double l;
                input(s.x, s.y, dir.x, dir.y, l);
                int cur = 0, ans = 0;
                p[0] = s;
                memset(lst_id, 0, sizeof(lst_id));
                memset(lst_l, 0, sizeof(lst_l));
                sort(cent[0].begin(), cent[0].end(), [](vec a, vec b){
                    return clockwise_cmp(a - p[0], b - p[0]);
                });
                // cerr << fixed << setprecision(20);
                while(true){
                    // cerr << cur << endl;
                    ans++;
                    auto it = lower_bound(cent[cur].begin(), cent[cur].end(), dir, [&](vec a, vec b){
                        return clockwise_cmp(a - p[cur], b - p[cur]);
                    });
                    if(it == cent[cur].end()) it = cent[cur].begin();
                    int x = 0;
                    while((*it - p[cur]).len() > l && x < n){
                        it++, x++;
                        if(it == cent[cur].end()) it = cent[cur].begin();
                    }
                    if(x == n) break;
                    dir = *it + *it - p[cur];
                    l -= (*it - p[cur]).len();
                    int nxt = id[*it];
                    if(lst_id[cur][nxt]){
                        long double cyc = lst_l[cur][nxt] - l;
                        int cnt = ans - lst_id[cur][nxt];
                        int k = l / cyc;
                        // cerr << cyc << ' ' << k << endl;
                        l -= k * cyc;
                        ans += k * cnt;
                    }
                    lst_id[cur][nxt] = ans, lst_l[cur][nxt] = l;
                    cur = nxt;
                }
                write(ans), puts("");
            }
        }
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}