贪心策略求助
  • 板块P2074 危险区域
  • 楼主lg128
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/16 14:57
  • 上次更新2024/8/16 15:56:54
查看原帖
贪心策略求助
1299571
lg128楼主2024/8/16 14:57

为什么不能找到最靠近中心的炸弹坐标,以t为半径的圆会覆盖最多的点,然后取这种坐标计算出圆内包含的点数呢

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int main(){
    double n,m,k,t;
    cin>>n>>m>>k>>t;
    double x,y;
    double minn=2e10;
    double xmid=(n+1)/2.0,ymid=(m+1)/2.0;
    double ax,ay;
    for(int i=0;i<k;i++){
        cin>>x>>y;
        double dis=sqrt((x-xmid)*(x-xmid)+(y-ymid)*(y-ymid));
        if(dis<=minn){
            minn=dis;
            ax=x,ay=y;
        }
    }
    cout<<ax<<' '<<ay<<endl;
    long long ans=0;
    for(int i=ax-t;i<=ax+t;i++){
        for(int j=ay-t;j<=ay+t;j++){
            if(i<1||i>n||j<1||j>m) continue;
            double d=sqrt((ax-i)*(ax-i)+(ay-j)*(ay-j));
            if(d<=t) ans++;
        }
    }
    cout<<ans;
    return 0;
}
2024/8/16 14:57
加载中...