洛谷T8115 毁灭

题目描述

YJC决定对入侵C国的W国军队发动毁灭性打击。将C国看成一个平面直角坐标系，W国一共有n^2个人进入了C国境内，在每一个(x,y)(1≤x,y≤n)上都有恰好一个W国人。YJC决定使用m颗核导弹，每一颗核导弹将杀死某个圆内所有的W国人，恰好在圆上也会被杀死。现在YJC想知道，在这一轮核打击之后，还有多少个W国人在C国境内。

输入输出格式

输入格式：

第一行包含两个整数n和m，意思如题所示。

接下来m行每行三个整数x,y和r，表示以(x,y)为圆心，r为半径的圆圆内和圆上的W国人被全部杀死。

输出格式：

一行，包含一个整数，表示幸存的W国人个数。

输入输出样例

输入样例#1：

输出样例#1：

说明

第一枚导弹杀死了(1,2)、(2,1)、(2,2)、(2,3)、(3,2)上的W国人，第二枚导弹杀死了(1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(3,1)上的W国人，只剩下(3,3)上的W国人没有被杀死。

对于50%的数据，满足n,m≤50。

对于100%的数据，满足1≤x,y≤n≤5000，0≤r≤n，1≤m≤5000。

还是码力问题以后不确定还是要写暴力啊QAQ不能太自信没对拍就交啊

——————————————————————————————————

这道题很容易想到的一个暴力就是枚举每一个核弹和每一个点（这样的复杂度是o（nnm））

很明显只能拿五十分

那么我们可以想着降一维考虑每一行和每一个核弹的关系利用差分就很容易实现辣

我的方法呢是每读入一个核弹就枚举所有他能覆盖到的行数枚举的方向大概是这样

利用勾股定理可以算出他和直线的交点可以发现两个交点构成的线段长度是递减的

然后就很好实现辣

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,ans;

int sum[][];

int main()

{

    n=read(); m=read();

    for(int k=;k<=m;k++){

        int x=read(),y=read(),r=read();

        for(int i=,j=r;i<=r;i++){

            int mx=r*r-i*i;

            while(j*j>mx) j--;

            int L=y-j,R=y+j;

            if(L<) L=;

            if(R>n) R=n;

            if(x-i>=) sum[x-i][L]++,sum[x-i][R+]--;

            if(x+i<=n) sum[x+i][L]++,sum[x+i][R+]--;

        }

    }

    for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

      ans+=bool(sum[i][j]+=sum[i][j-]);

    printf("%d\n",n*n-ans);

    return ;

}

巴特西

洛谷T8115 毁灭

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章