P177PROA - ROUND 7A - Một cái đinh rỉ !

Link Sub: https://www.spoj.com/PTIT/problems/P177PROA/
Người Gửi: Dương Lee

• Problem:

Lúa rất thích Lều, nhưng Lều không muốn xao nhãng việc học. Biết Lúa rất dốt toán, nhất là hình học nên Lều ra cho Lúa một bài toán và nếu Lúa không giải được thì sẽ cho Lúa một cơ hội.  
Lều cho Lúa một hình tròn có bán kính r, tâm của nó được đặt ở tọa độ x0, y0, và một chiếc đinh rỉ. 
Và yêu cầu phải đưa tâm hình tròn đến tọa độ x1,y1.  Biết rằng : Lúa chỉ được di chuyển hình tròn bằng cách cắm chiếc đinh vào mép của hình tròn và xoay hình tròn, và Lúa phải thực hiện với số lần cắm đinh ít nhất.  
Đương nhiên làm sai là chuyện đơn giản, “nhưng hôm nay là cá tháng Tư nên chắc Lều đang nói ngược thôi -_- “ . Hãy giúp Lúa giải bài toán này nhé.

Input

Một dòng duy nhất 5 số nguyên r,x0,y0,x1,y1. (1 ≤ r ≤ 105,  - 105 ≤ x, y, x', y' ≤ 105)

Output

In ra một số nguyên là số lần cắm đinh ít nhất để hoàn thành yêu cầu

Example:

Input

2 0 0 4 0

Output:

1

Input

4 1 2 1 2

Output:

0

Giải thích : Test 2 0 0 4 0
Như hình dưới : sẽ chỉ cần một lần cắm đinh và xoay.

Output:

• Solution:

Hix, cứ trâu thui bạn :(

• Code:

https://ideone.com/n7gR4i

C++:

#include <iostream>
#include <math.h>
using namespace std;
 
int main ()
{
    long long r, x0, y0, x1, y1;
    cin>>r>>x0>>y0>>x1>>y1;
    long long d = (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0);
    double k=sqrt(d);
 
    if (x1==x0 && y1==y0)
    {
        cout<<"0";
    }
    else
    {
        if ((k/2)<=r)
            cout<<"1";
        else
        {
            long long dem=0;
            do
            {
                k=k-(double)(r*2);
                dem++;
           }
            while (k/2>r);    		
            
            cout<<dem+1;	
    	}	
    }
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts