自动搬运

查看原文

来自洛谷，原作者为

	shinzanmono QQ: 2162579766||欢歌载舞，交换比特，共同庆祝

搬运于2025-08-24 23:16:58，当前版本为作者最后更新于2025-06-19 13:17:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先判掉无解（$w^2+h^2>4r^2$）。

如果横放 $i$ 列，那最多能放 $\left\lfloor\dfrac{\sqrt{4r^2-i^2w^2}}h\right\rfloor$ 行。答案即为 $\max_{i=0}^{\lfloor2r/w\rfloor}i\left\lfloor\dfrac{\sqrt{4r^2-i^2w^2}}h\right\rfloor$。考虑后面这个东西如果去掉下取整，其最值是简单的（取导求极值点）。合理猜想有下取整的极值点和原极值点差的不远，对一个邻域 $[p-B,p+B]$ 枚举求值即可。笔者的 $B$ 取 $10000$。

#include<iostream>
#include<algorithm>
using ll=long long;
ll sqrt(ll x){
  ll p=__builtin_sqrtl(x);
  while(p*p<=x)p++;
  while(p*p>x)p--;
  return p;
}
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin>>t;
  while(t--){
    ll rad,w,h;
    std::cin>>rad>>w>>h;
    if(w*w+h*h>4*rad*rad){
      std::cout<<"0\n";
      continue;
    }
    if(w<h)std::swap(w,h);
    auto ff=[&](ll x){return sqrt(4*rad*rad-w*w*x*x)/h*x;};
    ll l=sqrt(2*rad*rad/w/w),ans=0,B=10000;
    for(ll i=std::max(1ll,l-B);i<=std::min(2*rad/w,l+B);i++)ans=std::max(ans,ff(i));
    std::cout<<ans<<"\n";
  }
  return 0;
}