题解：P12631 [NAC 2025] Solar Farm

· · 题解

先判掉无解（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;
}