COJ 1687:Set_TinyMind

题意：在第一象限，所有坐标都为整数，有N个点有哥布林，再有M个圆，圆心半径已知，在圆内的哥布林会挂掉，问最后剩几个哥布林活着

思路：这里要注意到，虽然N和M很大，但是r很小，坐标范围也不大（1e4）

我们对于每一个x轴上的整数点开一个set，保存在这条线上的哥布林的纵坐标

对于每一个圆，我们枚举它覆盖的x范围[x-r,x+r]，对于每一个i值，求出覆盖的y的范围low，high

再在相应的Set里求出[low,high]里的元素个数，加到cnt里，再全部erase掉

最后答案就是N-cnt咯

注意要用multiset，因为有的哥布林坐标是重复的

#include"cstdio"
#include"queue"
#include"cmath"
#include"stack"
#include"iostream"
#include"algorithm"
#include"cstring"
#include"queue"
#include"map"
#include"set"
#include"vector"
#define ll long long
#define mems(a,b) memset(a,b,sizeof(a))
#define ls pos<<1
#define rs pos<<1|1
 
using namespace std;
const int MAXN = 10500;
const int MAXM = 100500;
const int INF = 0x3f3f3f3f;
 
struct node{
    int x,y,r;
}g[MAXM],p[2*MAXN];
 
multiset<int> s[MAXN];
int ans;
 
void Clear(int x,int y,int r){
    for(int i=x-r<=0?0:x-r;i<=x+r;i++){
        int h=floor(sqrt((double)r*r-(x-i)*(x-i)));
        multiset<int>::iterator l=s[i].lower_bound(y-h);
        multiset<int>::iterator r=s[i].upper_bound(y+h);
        if(l!=r){
            multiset<int>::iterator L=l;
            for(;L!=r;L++) ans++;
            s[i].erase(l,r);
        }
    }
}
 
int main(){
    int n,m;
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++) scanf("%d %d",&g[i].x,&g[i].y);
        for(int i=0;i<MAXN;i++) s[i].clear();
        for(int i=0;i<n;i++) s[g[i].x].insert(g[i].y);
        scanf("%d",&m);
        for(int i=0;i<m;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].r);
        ans=0;
        for(int i=0;i<m;i++) Clear(p[i].x,p[i].y,p[i].r);
        printf("%d\n",n-ans);
    }
    return 0;
}

View Code

优质内容筛选与推荐>>
1、后台启动mysql
2、mac 终端常用命令
3、javaOO11-13：OSI模型、TCP/IP模型、协议
4、善待Erlang 代码 -- 巧用 user_default
5、常用 Git 命令清单

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看