小清新几何题

· · 题解

题意：给定长方形长为 A，宽为 B，A,B\in[1,1000]\cap\mathcal{Z}，求最大的等边三角形使其可以放在长方形内，输出边长。

容易发现答案具有单调性，所以可以二分三角形边长。

这里有一个结论，就是一定存在某一顶点与长方形端点重合的最优解，因为如果不是则可以将三角形平移至某一顶点与长方形端点重合且边长不变，仍在长方形内。

而且最优解的另外两个顶点也一定在长方形的边上。

所以考虑如何检验答案合法性，这里参考题面上的图：

发现该三角形的两侧会形成两个直角三角形，假如我们已经知道三角形边长，那么我们就知道了两侧直角三角形的角度，事实上，只要两个角度之和不超过 \dfrac\pi 6 就是合法的，因为此时中间的夹角不低于 \dfrac\pi 3，可以缩小至 \dfrac\pi 3 使其成为等边三角形。

于是我们在 O(\log(\dfrac{\max\{A,B\}}\Delta)) 的时间复杂度内得到了答案：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pr=pair<int,int>;
const int N=1e6+6;
int n,m,T,a[N],d[N],ans;
basic_string<int>lk[N];
int q[N],l,r;
bitset<N>vs;
int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y;
    int A,B;
    cin>>A>>B;
    function<bool(ld)>ck=[&](ld d){
        ld L=d<A?0:acosl(A/d),R=d<B?0:acosl(B/d);
        ld res=acosl(-1)/2;
        res-=L,res-=R;
        return res>acosl(-1)/3;
    };
    ld L=min(A,B),R=10000,md,rl;
    while(R-L>1e-15){
        md=(L+R)/2;
        if(ck(md))rl=md,L=md+1e-17;
        else R=md-1e-17;
    }
    printf("%.15Lf\n",rl);
    return 0;
}