首页 > 试题广场 >

搬圆桌

[编程题]搬圆桌

热度指数：16682 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有一张半径为r的圆桌，其中心位于(x,y)，现在他想把圆桌的中心移到(x1,y1)。每次移动一步，都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。

输入描述:

一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000)

输出描述:

输出一个整数，表示答案

示例1

输入

2 0 0 0 4

输出

算法知识视频讲解

牛客836372号

import java.util.Scanner;
/**
 * 解题思路：利用贪心算法，我们知道每次移动的最大距离是直径（即2*r）
 * 不能AC的原因，如果我们直接计算出两点的距离，然后除以直径求解，测试数据只能通过80%
 * 这是在计算距离时发生了溢出的情况
 * 如何让其不溢出，可以先将两点的x轴与y轴坐标的距离除以直径取余数得到转换后的距离
 * 经过这个转换，所需要移动的步数为x轴与y轴坐标的距离除以直径取整所得数之和
 */
public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int r = scanner.nextInt();
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			int x1 = scanner.nextInt();
			int y1 = scanner.nextInt();	
			//为了防止计算距离时，大数相乘溢出，将x1-x和y1-y之间的距离转换到直径的范围内
			double dx=Math.abs((x1-x))%(2*r);
			double dy=Math.abs((y1-y))%(2*r);
			double s=Math.sqrt(dx*dx+dy*dy);
			//(int)(Math.abs((x1-x))/(2*r))与(int)(Math.abs((y1-y))/(2*r))
			//分别表示我们将x1-x和y1-y之间的距离转换到直径的范围内所需要移动的步数
			int step=(int) (s/(2*r))+(int)(Math.abs((x1-x))/(2*r))+(int)(Math.abs((y1-y))/(2*r));
			//当最后移动的距离不能被直径整除时，我们还要额外再移动一次
			if (s%(2*r)!=0) {
				step++;
			}
			System.out.println(step);		
		}
		scanner.close();
	}
}

发表于 2016-10-01 09:30:30 回复(5)

Zenas

//当初是在杭电acm的acmcoder网上考的，按照acm的“标准”，while循环输入。

#include <iostream>

#include <cmath>

usingnamespace std ;

int main(int argc, const char * argv[]) {

// insert code here...

int r, x, y, x1, y1;

double length, lx, ly, s;

while (cin>>r>>x>>y>>x1>>y1) {

lx = (x1-x)>=0 ? (x1-x) : (x-x1);

ly = (y1-y)>=0 ? (y1-y) : (y-y1);

length = sqrt(lx*lx + ly*ly);

s = length/(2*r);

int t = (int)s;

if (s - t > 0)

cout << t+1 <<endl;

else

cout << t << endl;

}

return 0;

}

编辑于 2015-09-22 15:29:41 回复(5)

牛客251340号

#include <iostream>
#include <math.h>
using namespace std;
 
int main(){
    float r,x,y,x1,y1;
    while(cin>>r>>x>>y>>x1>>y1){
        if(r<1) {cout<<0<<endl;continue;}
         
        double distance = sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
        float tmp = distance/2/r;
        int result = ceil(tmp);
        //int result = ceil(distance/2/r); 两句合起来就不行了，是为什么？
        cout<<result<<endl;
    }   
    return 0;
}

发表于 2015-10-10 19:32:31 回复(2)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int r,x,y,x1,y1;     while(cin>>r>>x>>y>>x1>>y1)     {         double d = sqrt(pow(x1-x,2) + pow(y1-y,2));         cout<<(int)ceil(d/(2*r))<<endl;     }     return 0;
}

发表于 2017-11-22 00:41:10 回复(0)

蓝魔4

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    double r,x1,x2,y1,y2;
    while(cin>>r>>x1>>y1>>x2>>y2)
    {
        double r1=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
        cout<<int(r1/(2*r))<<endl;
    }
    return 0;
}

发表于 2017-06-29 09:36:11 回复(1)

KKsama

//先无限沿着圆心连线向目标圆心移动，在<=4*r的时候只需两部就ok

#include <iostream>

using namespace std;

int main()

{

float x, y, x1, y1, r;

while (cin >> r >> x >> y >> x1 >> y1)

{

float dx;

dx = sqrt((x1 - x)*(x1 - x) + (y1 - y)*(y1 - y));

int count = 0;

if (dx <= 2 * r)

{

count++;

}

else if (dx <= 4 * r)

{

count += 2;

}

else

{

while (dx > 4 * r)

{

dx -= (2 * r);

count++;

}

count += 2;

}

cout << count << endl;

}

发表于 2017-05-10 14:01:21 回复(0)

Aurora1

from math import sqrt

while 1:
    try:
        s = raw_input()
    except:
        break
    r, x, y, x1, y1 = map(int, s.split())
    d, cnt = sqrt((x1 - x) ** 2 + (y1 - y) ** 2), 0
    while 1:
        d -= 2 * r
        if d <= 0:
            cnt += 1
            break
        cnt += 1
    print cnt

发表于 2017-05-01 10:30:25 回复(0)

H掠影

欺负咱没有上过小学吗？不知道三角形两边之和大于第三边？

#include<iostream>

#include<math.h>

using namespace std;

int main()

{

int r,x,y,x1,y1;

while(cin>>r>>x>>y>>x1>>y1)

{

int distance=sqrt(pow((x1-x),2)+pow((y1-y),2));

int rel=distance/(2*r);

cout<<rel<<endl;

}

return 0;

}

发表于 2017-04-01 22:36:45 回复(0)

SXISZERO

/*
每次旋转，圆心(x,y)的落点范围就是以(x,y)为圆心，半径为2r的圆。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define sqr(x) ((x)*(x))
double x,y,xa,ya;
int r;

int main()
{
    while(~scanf("%d%lf%lf%lf%lf",&r,&x,&y,&xa,&ya)){
        double a=sqrt(sqr(x-xa)+sqr(y-ya));
        int num=ceil(a/(2*r));
        printf("%d\n",num);
    }
    
    return 0;
}

发表于 2017-03-18 11:47:06 回复(0)

Holiday_12138

/*我觉得这是一道数学题 = =。
    沿着边缘旋转，每次移动，圆心可以移动以旧圆心为圆心，2r为半径的圆范围内任意一点
所以每次沿着起点和终点连线移动，每次2r，不足2r算1次。
所以ceil（d/2r）即可
*/
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        int r,x,y,x1,y1;
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            r=sc.nextInt();
            x=sc.nextInt();
            y=sc.nextInt();
            x1=sc.nextInt();
            y1=sc.nextInt();
            double d=Math.sqrt(Math.pow(x1-x, 2)+Math.pow(y1-y, 2));
            int res=(int) Math.ceil(d/(2*r));
            System.out.println(res);
        }
    }
}

发表于 2016-12-29 15:48:38 回复(0)

Alex-大伟


	importjava.util.Scanner;



	importjava.math.BigInteger;



	 



	publicclassMain {



	 



	    /**



	     * @param args



	     */



	    publicstaticvoidmain(String[] args) {



	        // TODO Auto-generated method stub



	        Scanner scanner = newScanner(System.in);



	        while(scanner.hasNext()) {



	            intr = scanner.nextInt();



	            intx = scanner.nextInt();



	            inty = scanner.nextInt();



	            intx1 = scanner.nextInt();



	            inty1 = scanner.nextInt();



	            System.out.println(step(r, x, y, x1, y1));



	        }



	    }



	 



	    publicstaticintstep(intr, intx, inty, intx1, inty1) {



	        BigInteger a = newBigInteger(String.valueOf(x1 - x)).multiply(newBigInteger(String.valueOf(x1 - x)));



	        BigInteger b = newBigInteger(String.valueOf(y1 - y)).multiply(newBigInteger(String.valueOf(y1 - y)));



	        BigInteger sum =  a.add(b);



	         



	        BigInteger maxPerDis = newBigInteger(String.valueOf(2* r * 2* r));



	        return (int) Math.sqrt(Math.ceil(Double.parseDouble(sum.divide(maxPerDis).toString())));



	    }



	}

发表于 2016-09-28 09:20:25 回复(0)

wsxoo

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int getDis(int tmp,int tmp1){
    if( (tmp>=0&&tmp1>=0) || (tmp<0&&tmp1<0) ){
        return abs(tmp-tmp1);
    }else{
        if(tmp>0){
            return (tmp-tmp1);
        }else{
            return (tmp1-tmp);
        }
    }
}
int main(void){
    int r,x,y,x1,y1;
   	int yDis,xDis;
    int cnt=0;
    double xieBian1;
    double tmpx,tmpy;
    double sumx,sumy;
    while(cin>>r>>x>>y>>x1>>y1){
    	xDis = getDis(x1,x);
       	yDis = getDis(y1,y);
        if( 0 == xDis || 0 == yDis){//(x,y)和(x1,y1)在同一条直线上
            xieBian1 = xDis==0?yDis:xDis;
        }else{
            xieBian1 = sqrt((double)(xDis*xDis+yDis*yDis));
        }
       	
       	tmpx = (double)r*(xDis/xieBian1);
    	tmpy = (double)r*(yDis/xieBian1);
  	    sumx = 0;
        sumy = 0;
      	cnt = 0;
        //最少移动的步数便是沿着两点间的连线移动
        //由于题目给出的数据都是满足要求的，即沿着圆边上的点能移动到目的坐标(x1,y1)，所以这里不用判断
        //如果给出的数据不能移动到(x1,y1),只要判断跳出循环时sumx、sumy的值和xDis、yDis的值是否相等即可
        while( sumx<xDis || yDis>sumy ){
            if( sumx < xDis ){
                sumx += tmpx;
            }
            if( yDis > sumy ){
                sumy += tmpy;
            }
            
            cnt++;
        }
        cout<<cnt/2<<endl;
        
    }
    
    return 0;
}

发表于 2016-09-23 16:53:53 回复(0)

CiaoLiang

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>

using namespace std;
//注意数字范围别越界。输入采用long long型
int main(){
    long long r,x,y,x1,y1;
    while(cin>>r>>x>>y>>x1>>y1){
        double ret = ((x1-x)*(x1-x)+(y1-y)*(y1-y))/(4*r*r);
        ret = sqrt(ret);
        cout << ceil(ret)<<endl;
    }
    return 0;
}

发表于 2016-09-04 19:53:19 回复(0)

Jasooon

分情况讨论一下就OK了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
    int r,x,y,x1,y1;
    while(~scanf("%d%d%d%d%d",&r,&x,&y,&x1,&y1)){
        int dis = abs(y1-y)+abs(x1-x);
        if(dis<r){
            puts("2");
            continue;
        }
        if(dis<=2*r){
            puts("1");
            continue;
        }
        r = 2*r;
        int tmp = dis - r;
        tmp = tmp/r;
        tmp += (tmp%r != 0);
        printf("%d\n",tmp);
    }
}

发表于 2016-08-27 15:26:26 回复(1)

fight灬奋斗

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int r,x,y,x1,y1;
    while(cin>>r>>x>>y>>x1>>y1){
        double a=sqrt(pow(x1-x,2)+pow(y1-y,2));
        int R=ceil(a/2/r);
        cout<<R<<endl;
    }
    return 0;
}

发表于 2016-08-25 08:46:23 回复(0)

老石基

public static void main(String args[]){
        Scanner reader=new Scanner(System.in);
        while(reader.hasNextInt()){
            int r=reader.nextInt();
            int x=reader.nextInt();
            int y=reader.nextInt();
            int x1=reader.nextInt();
            int y1=reader.nextInt();
            int lx = Math.abs(x-x1);
            int ly = Math.abs(y-y1);
            int len = lx==0?ly:ly==0?lx:(int)Math.sqrt(lx*lx+ly*ly);
            int l = len/(2*r);
            int t = (int)l;
        	if (l - t > 0)
                 System.out.println(t+1);
        	else
                 System.out.println(t);
        }
  }

发表于 2016-04-14 15:42:11 回复(0)

贝叶斯

class moveTable {

	public int moveCount(int r,int x,int y,int x1,int y1) {
		double xDistance= Math.pow((x1-x), 2);
		double yDistance= Math.pow((y1-y), 2);
		double rDistance= Math.sqrt(xDistance+yDistance);
		int result=(int) Math.ceil(rDistance/(2*r));
		if (r<1|r>100000) {//其他限制条件略了.....
			return -1;
		}
		
		
		return result;
	}
    	public ststic void main(String[] args) {
		// TODO Auto-generated method stub
		moveTable move=new moveTable();
		System.out.println(move.moveCount(2,0,0,0,4));
	}
}

编辑于 2016-03-27 13:55:49 回复(0)

kiss90

//关键点：在距圆心（0，2*r]内，总能找到一个半径为r的圆与该圆相交。
//所以，距离在（0，2*r]内时，只需要一步即可。 #include <iostream>
#include <cmath>

using namespace std;

int main()
{
    float r,x,y,x1,y1;
    while(cin >>r>>x>>y>>x1>>y1){
        double len=sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
        double n1 = len/(2*r);
        int n = (int)n1;
        n==n1? cout<<n<<endl:cout<<n+1<<endl;
    }
    return 0;
}

编辑于 2016-03-15 21:08:38 回复(0)

程序远

每次可以移动的距离s的范围为(0, 2 * r]。另外，这里运用while循环接受所有输入。

发表于 2015-09-26 20:56:33 回复(1)

依影

 旋转一次最长距离是2*r；
求两点距离Length；(直接按勾股定理算，会测试不通过，可能参数比较大，平方就溢出了。可以预先判断x，y是否为零，直接得出距离)
cout<<(Length+2*r-1)/(2*r);

发表于 2015-09-23 13:35:06 回复(2)

提交观点

问题信息

贪心 C++工程师 2016 蘑菇街 Java工程师

来自：美丽联合2016研发工...

难度：

125条回答 99收藏 20178浏览

通过挑战的用户

查看代码

牛客50343...

2023-02-13 16:15:27
牛客61094...

2022-09-15 10:41:09
牛客65482...

2022-09-14 23:37:49
牛客52079...

2022-09-14 16:48:53
牛客31432...

2022-09-14 14:58:51

搬圆桌

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题