Goblin Garden Guards (思维)

2018-08-02

Goblin Garden Guards

题意

给n个哥布林的位置（x，y），给出m个圆，对于每一个圆，输出最大的不在圆内的哥布林数目。

由于哥布林的位置是整数，那么对于圆，可以预处理出距离圆心0~r范围内的x最大偏差值和y的最大偏差值，如果哥布林的x，y与圆心的偏差值有一者在最大偏差值之外，就cnt++。

看！代码

//拿的队友的代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long ll;
struct point
{
    int x,y;
}p[100010];
bool cmp(point a,point b)
{
    return a.y<b.y;
}
vector<int>v[100010];
vector<int>d[110];
void init()
{
    for(int r=1;r<=100;r++)
        for(int i=0;i<=r;i++)
            d[r].push_back((int)floor(sqrt(1.0*r*r-i*i)));
}
int main()
{
    init();
    int g,m,x,y,r;
    scanf("%d",&g);
    for(int i=0;i<g;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    sort(p,p+g,cmp);
    for(int i=0;i<g;i++)
        v[p[i].x].push_back(p[i].y);
    scanf("%d",&m);
    int ans=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&r);
        int left=max(0,x-r),right=min(10000,x+r);
        for(int dd=left;dd<=right;dd++)//横坐标
        {       
            int c=abs(dd-x);
            int yl=max(0,y-d[r][c]),yr=min(10000,y+d[r][c]);
            int pos1=lower_bound(v[dd].begin(),v[dd].end(),yl)-v[dd].begin();
            int pos2=upper_bound(v[dd].begin(),v[dd].end(),yr)-v[dd].begin();
            v[dd].erase(v[dd].begin()+pos1,v[dd].begin()+pos2);
            ans+=pos2-pos1;
        }
    }
    printf("%d\n",g-ans);
    return 0;
}