K Yet Another Problem About Pi

• 链接：K-Yet Another Problem About Pi_2021牛客暑期多校训练营8 (nowcoder.com)

• 题意：平面上有无穷个长，宽为的矩形方格。你有一条长度为​的曲线可以任意弯折，起点任意，求曲线最多经过的方格数目（不计边界）

• 先考虑最坏情况：对应时，我们不能越过任何一个方格，此时我们的最佳方案应该是以四个矩形方格的交点为起点，向周围走一圈，最小结果为4

• 如果我们能够越过方格，我们可以认为以下的所有情况都是有上方（结果为4）的情况推广而来，因为上述拿法是开局最佳。并且因为是无限循环小数，我们可以认为折线极其微小，但是真实存在，此时可以忽略折线的长度，我们有两种方案：

  • 走直线：取，走长度更小的一侧必然更优，此时每越过一个格子增加贡献为2
  • 走曲线：取，每越过一个格子增加贡献为3（即斜对角方格和其旁边紧挨两格）

• 可见的是，我们要协调上述两种操作，使得最后的贡献最多。并且可以知道的是：在使用上述操作时，仅有边界情况会影响操作的选择是否需要改变（如走直线变成走曲线）。所以这种变换操作最多存在两次（可以类比回退一步求更优值），所以直接枚举上述两种操作的存在次数，对取即可

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const double PI = acos(-1);
signed main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        double w, d, tmp, dis;
        ll ans = 0;
        scanf("%lf%lf", &w, &d);
        tmp = min(w, d);
        dis = sqrt(w * w + d * d);
        for(int i = 0; i <= 2; ++i) {
            //枚举直线数目
            if(i * tmp <= PI) ans = max(ans, (ll)(4 + 2 * i + floor((PI - tmp * i) / dis) * 3));
            // 枚举斜线数目
            if(i * dis <= PI) ans = max(ans, (ll)(4 + 3 * i + floor((PI - dis * i) / tmp) * 2));
        }printf("%lld\n", ans);
    }    
    return 0;
}