刷题记录:牛客NC16746神奇盘子

传送门:牛客

题目描述:

有一个神奇的盘子，形状为圆形。盘子上面爬着一个大象（视作一个点）。由于现实的扭曲，当大象在盘子某个直径的一端的时候，可以瞬间传送至直径的另一端。现在大象想去盘子上另外一点，问他最少需要移动多少距离。传送不计距离。
输入:
1
0 1
0 -1
输出:
0.000000000000
1
2
3
4
5
6
7

对于这道题,我的第一想法是用数学的思想去找出那个最适合的传送点,然而发现以我的实力并不能找到,所以我就换了一种方法.在介绍这种方法之前,我们先对这种贪心的思想做一个简单的小证明

对于一个圆盘,我们有起点和终点,我们现在的贪心想法是在圆盘上枚举一个点,然后计算每次从起点到终点和从起点到传送点,在从传送点到终点的距离的min值,为什么这样就是最优的呢,我们将一个圆盘显然是可以分成两半的(终点所在的一半与不在的一半),假设我们经过传送之后到达一个直径所对的另一个点,显然这个点要在终点的那一半才行,如果我们在进行一次传送的话肯定就是到达终点所对的另一个点了(距离显然增大),所以我们要不进行一次传送,要么就不进行传送.
并且因为我们的精度只有在1e-6而已,我们可以直接卡精度进行枚举,枚举范围是2Pi即可
而Pi的话我们可以使用反三角函数来求出,cosPi=-1,arcos(-1)=Pi

接下来是具体代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define Pi acos(-1)
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
double r;
double dist(double x1,double y1,double x2,double y2) {
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main() {
	cin>>r;
	double X1,Y1,X2,Y2;
	cin>>X1>>Y1>>X2>>Y2;double ans=dist(X1,Y1,X2,Y2);
	for(double i=0;i<=2*Pi;i+=1e-6) {
		double XX1=r*cos(i),YY1=r*sin(i);
		double XX2=-XX1,YY2=-YY1;
		ans=min(ans,dist(XX1,YY1,X1,Y1)+dist(XX2,YY2,X2,Y2));
	}
	printf("%.12lf", ans);	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41