Tour Guide 导游的算法

Question

Problem Description
You are working as a guide on a tour bus for retired people, and today you have taken your regular Nordic seniors to The Gate of Heavenly Peace. You let them have a lunch break where they could do whatever they like. Now you have to get them back to the bus, but they are all walking in random directions. You try to intersect them, and send them straight back to the bus. Minimize the time before the last person is in the bus. You will always be able to run faster than any of the tour guests, and they walk with constant speed, no matter what you tell them. The seniors walk in straight lines, and the only way of changing their direction is to give them promises of camphor candy. A senior will neither stop at nor enter the bus before given such a promise.

Input
A number of test cases consisting of: A line with an integer 1 ≤ n ≤ 8, the number of people on the tour. A line with an floating point number 1 < v ≤ 100, your maximum speed (you start in the bus at the origin). Then follow n lines, each containing four floating point numbers xi yi vi ai, the starting coordinates (-106 ≤ xi, yi ≤ 106), speed (1 ≤ vi < 100) and direction (0 ≤ ai < 2π) of each of the tour guests.

The input is terminated by a case with n = 0, which should not be processed. All floating point numbers in the input will be written in standard decimal notation, and have no more than 10 digits.

Output
For each test case, print a line with the time it takes before everybody is back in the bus (the origin). Round the answer to the nearest integer. The answer will never be larger than 106.

Sample Input
1
50.0
125.0 175.0 25.0 1.96
3
100.0
40.0 25.0 20.0 5.95
-185.0 195.0 6.0 2.35
30.0 -80.0 23.0 2.76
0

Sample Output
20
51

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 导入必要的库
library(Rcpp)
library(Rcpp::Rcpp)

# 定义函数
tour_guide <- function(n, v, x, y, vx, vy, angle) {
  # 初始化变量
  total_time <- 0
  current_position <- c(x, y)
  
  # 遍历每一名游客
  for (i in 1:n) {
    # 计算当前游客的位置
    position_x <- current_position[1] + vx * cos(angle[i]) 
    position_y <- current_position[2] + vy * sin(angle[i])
    
    # 如果游客已经到达目的地，则返回时间
    if (position_x == 0 & position_y == 0) return(total_time)
    
    # 更新游客的位置和速度
    current_velocity <- sqrt(vx^2 + vy^2)
    angle_change <- atan2(position_y, position_x) - angle[i]
    angle_change <- max(min(angle_change, 2*pi), -2*pi)
    angle[i] <- angle_change
    
    # 更新游客的速度和方向
    vx <- vx * cos(angle_change)
    vy <- vy * sin(angle_change)
    
    # 计算新的位置和速度
    new_position_x <- current_position[1] + vx * cos(angle[i])
    new_position_y <- current_position[2] + vy * sin(angle[i])
    new_velocity <- sqrt(vx^2 + vy^2)
    
    # 更新总时间和当前位置
    total_time <- total_time + abs(new_position_x - current_position[1]) + abs(new_position_y - current_position[2])
    current_position <- c(new_position_x, new_position_y)
  }
  
  # 返回总时间
  round(total_time)
}

# 示例输入
n <- 1
v <- 50.0
x <- 125.0
y <- 175.0
vx <- 25.0
vy <- 175.0
angle <- 1.96

# 调用函数并输出结果
tour_guide(n, v, x, y, vx, vy, angle)

这段代码使用了Rcpp库来实现C++代码的转换。在代码中，我们定义了一个tour_guide函数，它接受四个参数：游客的数量（n），车速（v），游客的起始坐标（x, y），以及游客的方向角（vx, vy, angle）。这个函数遍历每个游客，更新他们的位置和速度，并计算新的总时间和当前位置，直到所有游客都回到起点。最后，我们将这个函数调用来处理给定的示例输入。