Yet Another Problem About Pi
题意:
平面上有无穷个长,宽为w,d的矩形方格。你有一条长度为Π的曲线可以任意弯折,起点任意,求曲线最多经过的方格数目(不计边界)
思路:
先考虑最坏情况:对应max(w,d)>PI时,我们不能越过任何一个方格,此时我们的最佳方案应该是以四个矩形方格的交点为起点,向周围走一圈,最小结果为4
- 如果我们能够越过方格,我们可以认为以下的所有情况都是有上方(结果为4)的情况推广而来,因为上述拿法是开局最佳。并且因为是无限循环小数,我们可以认为折线极其微小,但是真实存在,此时可以忽略折线的长度,我们有两种方案:
- 走直线:取,走长度更小的一侧必然更优,此时每越过一个格子增加贡献为2
- 走曲线:取,每越过一个格子增加贡献为3(即斜对角方格和其旁边紧挨两格)
- 可见的是,我们要协调上述两种操作,使得最后的贡献最多。并且可以知道的是:在使用上述操作时,仅有边界情况会影响操作的选择是否需要改变(如走直线变成走曲线)。所以这种变换操作最多存在两次(可以类比回退一步求更优值),所以直接枚举上述两种操作的存在次数,对res取最大值即可
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const double PI = acos(-1);
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--){
double n,m;
cin>>n>>m;
int res=0;
double xie=sqrt(n*n+m*m);
double mi=min(n,m);
for(int i=0;i<3;i++){
if(i*mi<=PI){
res=max(res,(int)(4+i*2+floor((PI-i*mi)/xie)*3));
}
if(i*xie<=PI){
res=max(res,(int)(4+i*3+floor((PI-i*xie)/mi)*2));
}
}
cout<<res<<endl;
}
return 0;
}