容易想到二分,然后考虑如何放点使得边数最多。

容易想到,应该是尽量放成正方形,不够数量时就在正方形边缘绕。

达到图的边界就只能画长方形了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef long long LL;
using namespace std;
LL n,m,lim,ans;
LL Calc(LL cnt){
if(n==1) return cnt*2+2;
if(cnt==1) return 4;
if(cnt==2) return 6;
if(cnt==3) return 8;
if(cnt>n*n){
LL t1=(cnt-n*n)%n, t2=(cnt-n*n)/n;
return n*4+t2*2+(t1!=0)*2;
}
LL t1=sqrt(cnt);
return t1*4+(t1*t1!=cnt)*2;
}
bool check(LL k){
return k*(k-1)/2-(k*4-Calc(k))/2<=lim;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&lim);
ans=1; if(n>m) swap(n,m);
LL L=2, R=min(n*m,(LL)sqrt(lim*2)+n*4);
while(L<=R){
LL mid=(L+R)>>1;
if(check(mid)) L=mid+1, ans=mid; else R=mid-1;
}
check(19);
printf("%lld\n",ans);
return 0;
}