每日一题 7.17 [ZJOI2006]BOWL 碗的叠放

这是一道几何题吧（大概
n的范围很小 我们可以直接生成全排列来寻找堆叠碗最低的序列组合
两个碗的堆叠种类有6种（在代码里面都有注释 建议自己在纸上手画一遍
碗一个一个堆叠时 要计算与之前已经放的碗一起堆的高度
其中最高的高度就是真实高度（这一点是看别人题解才知道的.......
qwq 菜鸡没什么好说的了

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,k[N];
double r1[N],r2[N],h[N],f[N];
double qg(int x,int y)
{
    if(r2[x]<=r1[y]) return 0;///x全部在y里面
    if(r1[x]>=r2[y]) return h[y];///x全部在y外面
    if((r2[x]-r1[x])*h[y]<=(r2[y]-r1[y])*h[x])///x的斜率大于y
    {
         if(r1[x]<=r1[y]) return 0;///x能接触到y的底
         return (r1[x]-r1[y])*h[y]/(r2[y]-r1[y]);///不能接触到y的底
    }
    if(r2[x]<=r2[y])return max(0.0,double(h[y]*(r2[x]-r1[y])/(r2[y]-r1[y])-h[x]));///x全部在y里面（x斜率小于y）
    return max(0.0,double(h[y]-h[x]*(r2[y]-r1[x])/(r2[x]-r1[x])));///一部分在外面

}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>h[i]>>r1[i]>>r2[i];///r1 下低  r2 上低
        k[i]=i;
    }
    double ans=1000000000;
    do
    {
       double ins=0;
       for(int i=1;i<=n;++i)
       {
            f[i]=0;
            for(int j=1;j<i;++j)f[i]=max(f[i],f[j]+qg(k[i],k[j]));
            ins=max(ins,f[i]+h[k[i]]);
       }
       ans=min(ins,ans);
    }
    while(next_permutation(k+1,k+1+n));
    cout<<ans<<endl;
    return 0;
}