[SCOI2009]生日快乐

我一看到wxh大佬题单里一道斜率优化一道cdq就果断跳过，然后终于找到一道可做的了。

我一开始没看到相同面积，心想搜索时间复杂度怕是要爆炸，但也没想出其它方法，然后看了题解才发现是相同面积，那直接搜索就完事了。

因为面积相同，所以每次切的长宽一定是 $x\div cnt$的倍数（cnt是当前这块能分成几份），所以直接枚举在哪里切即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,x,y;

double dfs(double x,double y,int cnt) //长宽x,y;当前这一块要分成cnt块
{
    if (x>y) swap(x,y);
    if (cnt==1) return y/x;
    double ans=1e9;
    for (int i=1;i<cnt;i++) 
    {
        double piece=x/cnt*i;
        ans=min(ans,max(dfs(piece,y,i),dfs(x-piece,y,cnt-i)));
        piece=y/cnt*i;
        ans=min(ans,max(dfs(x,piece,i),dfs(x,y-piece,cnt-i)));
    }
    return ans;
}

int main()
{
    x=read(); y=read(); n=read();
    printf("%.6f",dfs(x*1.0,y*1.0,n));
    return 0;
}