解题思路

这是一道几何问题,主要思路如下:

  1. 问题分析:

    • 有一个半径为 的圆桌
    • 需要从点 移动到点
    • 每次移动一步后需要固定一点并旋转
    • 求最少需要移动几步
  2. 解决方案:

    • 计算两点之间的直线距离
    • 每步最多可以移动直径 的距离
    • 用距离除以直径得到最少步数
    • 如果不能整除需要向上取整
  3. 实现细节:

    • 使用勾股定理计算距离
    • 处理除法向上取整的情况
    • 注意浮点数精度问题

代码

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int r, x, y, x1, y1;
    // 处理多组输入
    while (cin >> r >> x >> y >> x1 >> y1) {
        // 计算两点间距离
        double distance = sqrt(pow(x-x1, 2) + pow(y-y1, 2));
        
        // 计算最少步数
        int result = distance / (2*r);
        // 如果不能整除,需要多走一步
        if(result * 2 * r < distance) {
            result++;
        }
        
        cout << result << endl;
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 处理多组输入
        while (sc.hasNext()) {
            int r = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            
            // 计算两点间距离
            double distance = Math.sqrt(Math.pow(x-x1, 2) + Math.pow(y-y1, 2));
            
            // 计算最少步数
            int result = (int)(distance / (2*r));
            // 如果不能整除,需要多走一步
            if(result * 2 * r < distance) {
                result++;
            }
            
            System.out.println(result);
        }
        sc.close();
    }
}
import math

def min_steps(r, x, y, x1, y1):
    # 计算两点间距离
    distance = math.sqrt((x-x1)**2 + (y-y1)**2)
    
    # 计算最少步数
    result = int(distance / (2*r))
    # 如果不能整除,需要多走一步
    if result * 2 * r < distance:
        result += 1
    
    return result

def main():
    # 处理多组输入
    while True:
        try:
            r, x, y, x1, y1 = map(int, input().split())
            print(min_steps(r, x, y, x1, y1))
        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法:数学计算
  • 时间复杂度: - 只需要简单的数学计算
  • 空间复杂度: - 只需要常数空间