[编程|1500分] 神奇盘子

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
Special Judge,64bit IO Format: %lld

题目描述

有一个神奇的盘子,形状为圆形。盘子上面爬着一个大象(视作一个点)。由于现实的扭曲,当大象在盘子某个直径的一端的时候,可以瞬间传送至直径的另一端。现在大象想去盘子上另外一点,问他最少需要移动多少距离。传送不计距离。

输入描述:

第一行一个整数r(1 <= r <= 1000)代表盘子的半径。
接下来两行两个整点分别代表大象所在的位置和大象目标的位置坐标。保证两个点都在圆内(可能在边界上),圆心在点(0, 0)上。

输出描述:

输出一个实数,代表大象最短需要移动多少距离。和标程相对或绝对相差1e-6都算正确。

示例1

输入

1
0 1
0 -1

输出

0.000000000000

示例2

输入

4
3 0
-3 0

输出

2.000000000000

说明

301312_1529636221266_A0DE9FC5C63D12A31918C9EE11768FDD.png

示例3

输入

100
-59 76
3 69

输出

62.393909959226

题解

中档题。个人认为是先取出一个大概的区间然后二分查找出答案的但是这样写太麻烦了于是……暴力出奇迹!直接分成足够多份暴力枚举即可。

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
const double n = 1000000;
const double pi=3.141592653589793238; 
double ans;
double r, xd1, yd1, xd2, yd2;
double pf(double a) {
    return a * a;
}
int main() {
    cin >> r;
    cin >> xd1 >> yd1;
    cin >> xd2 >> yd2;
    ans = sqrt(pf(xd1 - xd2) + pf(yd1 - yd2));
    for (int i = 0; i <= n; i++) {
        ans=min(ans,sqrt(pf(cos(2 * pi*i / n+pi)*r - xd2) + pf(sin(2 * pi*i / n+pi)*r - yd2)) +sqrt(pf(cos(2 * pi*i / n)*r - xd1)+ pf(sin(2 * pi*i / n)*r - yd1)));
    }
    printf("%lf",ans);
}


标签: none

添加新评论