K Yet Another Problem About Pi
https://ac.nowcoder.com/acm/contest/11259/K
大致翻译:
给出每个区域的长和宽,求长度为π \piπ的线(形状任意只要是相连的就可以)最多可以经过几个区域。
分析:
首先要知道沿着斜线或者边走,可以将区域所划分的先看成无限细,把pi拿出一点点(0.000000……0001)到它旁边的格子就满足线到区域里
如图:
线的起始位置:在四个区域的交叉位置为最优,因为此时它可以经过四个区域;(4)
此时这根线主要有两种走法:(宽<=长)
1.沿着区域的宽(直线)走,每经过一条宽即经过两个区域;(2)
2.沿着区域的斜线(对角线)走,每经过一次交叉位置可以在原有区域上新增三个区域;(3)
得到这两个走法后先判断哪种方案比较优(贪心思想);
1.若走直线优,在走到最后一次宽时判断此时能不能把最后一次宽改为走斜线,即:宽+剩余的线能不能走一次对角线(因为最后一次的宽只能加2,但斜线可以加3,明显斜线好);
2.若走斜线优:
判断一:在走到最后一次斜线时判断剩下的线能不能走一次宽(因为宽必然比斜线短(三角形知识不解释)),若可以就可以在原区域基础上新增2;
若上述不满足判断二:在走到最后一次斜线时判断此时能不能把最后一次斜线改为走两次宽,即:斜线+剩余的线能不能走两次宽(因为最后一次的斜线只能加3,但两次宽可以加4);
代码:
1、
#include<bits/stdc++.h>
using namespace std;
double pi=acos(-1);
typedef long long ll;
int main(){
int t;
cin>>t;
while(t--){
double c,k;
cin>>c>>k;
double x=sqrt(c*c+k*k);
if(k>c)k=c;
ll ans=4;
if(k>pi){
cout<<ans<<endl;
continue;
}
double xh=x/3,zh=k/2;//判断两种方案哪个更优(即获得同样收益时谁用的线少(短))
if(xh>zh){//沿宽走
ll zg=ll(pi/k);
ans+=zg*2;
if(pi-(zg-1)*k>x)ans++;
}else{//沿对角线走
ll xg=ll(pi/x);
ans+=xg*3;
if(pi-xg*x>k)ans+=2;
else if(pi-(xg-1)*x>2*k)ans++;
}
cout<<ans<<endl;
}
return 0;
}
using namespace std;
double pi=acos(-1);
typedef long long ll;
int main(){
int t;
cin>>t;
while(t--){
double c,k;
cin>>c>>k;
double x=sqrt(c*c+k*k);
if(k>c)k=c;
ll ans=4;
if(k>pi){
cout<<ans<<endl;
continue;
}
double xh=x/3,zh=k/2;//判断两种方案哪个更优(即获得同样收益时谁用的线少(短))
if(xh>zh){//沿宽走
ll zg=ll(pi/k);
ans+=zg*2;
if(pi-(zg-1)*k>x)ans++;
}else{//沿对角线走
ll xg=ll(pi/x);
ans+=xg*3;
if(pi-xg*x>k)ans+=2;
else if(pi-(xg-1)*x>2*k)ans++;
}
cout<<ans<<endl;
}
return 0;
}
2、
#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const double PI = acos(-1);
int main() {
int t;
scanf("%d", &t);
while (t--) {
double w, d, tmp, dis;
ll ans = 0;
scanf("%lf %lf", &w, &d);
tmp = min(w, d);
dis = sqrt(w * w + d * d);
for (int i = 0; i <= 2; ++i) {
//枚举直线数目
if (i * tmp <= PI) ans = max(ans, (ll)(4 + 2 * i + floor((PI - tmp * i) / dis) * 3));
// 枚举斜线数目
if (i * dis <= PI) ans = max(ans, (ll)(4 + 3 * i + floor((PI - dis * i) / tmp) * 2));
}
printf("%lld\n", ans);
}
return 0;
}
#define endl '\n'
typedef long long ll;
using namespace std;
const double PI = acos(-1);
int main() {
int t;
scanf("%d", &t);
while (t--) {
double w, d, tmp, dis;
ll ans = 0;
scanf("%lf %lf", &w, &d);
tmp = min(w, d);
dis = sqrt(w * w + d * d);
for (int i = 0; i <= 2; ++i) {
//枚举直线数目
if (i * tmp <= PI) ans = max(ans, (ll)(4 + 2 * i + floor((PI - tmp * i) / dis) * 3));
// 枚举斜线数目
if (i * dis <= PI) ans = max(ans, (ll)(4 + 3 * i + floor((PI - dis * i) / tmp) * 2));
}
printf("%lld\n", ans);
}
return 0;
}