P2074危险区域我有个新思路但是只有90分。。

回复帖子

@slx0604 2019-05-15 21:45 回复

题目

思路就是:因为每个炸弹的范围一样,那很显然越靠近中心能影响的范围越大,那么我们就找离中心最近的点就好

过的点不到10ms,比题解的枚举快很多 我发题解了,还没过审,如果大家看到题解别惊讶。。

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,k,t;
struct dis //结构体, x,y记录坐标 ,distance记录与城市中心的距离用于排序 
{
    int x,y;
    float distance;
}d[N];
int ans;
float c_x,c_y;
void centre() //计算城市的中心,为了避免奇偶的问题就用了浮点 
{
    c_x=n*1.0 /2;
    c_y=m*1.0 /2;
}
float get_dist(int xx,int yy) //计算该炸弹点离城市中心的距离 
{
    float lx=abs(xx*1.0-c_x);
    float ly=abs(yy*1.0-c_y);
    return sqrt(lx*lx +ly*ly);
}
bool cmp(dis a,dis b) //根据距离排序找到最近的 
{
    return a.distance>b.distance;
}
double getdis(int x,int y,int a,int b)  
{
    return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int main()
{
    cin>>n>>m>>k>>t;
    centre();
    for (int i=1;i<=k;i++) //读入全部数字算出distance 
    {

        cin>>d[i].x>>d[i].y;
        d[i].distance=get_dist(d[i].x,d[i].y);
    }

    sort(d+1,d+1+k,cmp); //排序 
    int x=d[k].x; //得到答案点 
    int y=d[k].y;
    //下面就是直接拿其他大佬的代码算该点的答案了 
    for(int i=max(x-t,1);i<=min(n,x+t);i++) 
            for(int j=max(y-t,1);j<=min(m,y+t);j++) 
                if(getdis(i,j,x,y)<=t)
                    ans++;
    cout<<ans<<endl;
    return 0;
}
@slx0604 2019-05-15 21:46 回复

当然我不认为我是新思路,emmmmm反正我题解里没看见

@s_r_f 2019-05-15 22:14 回复

你能证明它的正确性吗

@slx0604 2019-05-15 22:21 回复

@s_r_f 在相同的范围下,如果影响范围有区别,肯定是因为太靠近城市边缘啊,所以越中心越多嘛

@yzhang 2019-05-15 22:27 回复

我觉得这毫无正确性可说哇