题面:已知网格中的长和宽,一个人可以走π km,求最多经过多少区域。
解析:因为π 是无限不循环小数,网格的长宽是有限的,所以问题可以相当为人只走交叉点,因为只需要轻微的扰动就可以经过点周围的四片区域。
而相邻的点的距离只有三种,长,宽,对角线,增加的区域则是2,2,3。即求3x+2y的最大值,在ax+by<= π的条件下,其中 。
求最大值的方法,可以采用枚举。而边界为2,是因为,操作要么走直线,要么走对角线,其中操作改变只可能是边界问题,因为有两端所以最多只可能变化两次操作。
代码:
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
const double pi=acos(-1);//不能直接赋值,不然精度不行
int t;
double w,d,d1,w1;
int main(){
cin>>t;
int f;
while(t--){
cin>>w>>d;
w1=max(w,d);
d1=min(w,d);
double t1=sqrt(d1*d1+w1*w1);
double t2=d1;
int ans=0;
for(int i=0;i<=2;i++)
{
if(pi-i*t1>0)ans=max(ans,i*3+int((pi-i*t1)/t2)*2);
if(pi-i*t2>0)ans=max(ans,i*2+int((pi-i*t2)/t1)*3);
}
cout<<ans+4<<endl;
}
}


京公网安备 11010502036488号