Color it (简单扫描)

2018-08-09

Color it

题意

给你一个表格样，再给出m个圆，满足式子：$\sqrt{(i-x_c)^2+(j-y_c)^2}\le{r}$ 的，都要染成黑色，问你最后没有被染色的格子数。

思路就是简单模拟一下扫描线的操作，可以先对每一个圆，处理出圆内列对应的扫描线的长度，存在相应的列中。然后再遍历每一列，对于列中存在的扫描线，按照l小r大排序，然后如果这个区间的l要大于上个区间的r，ans就减去this.r-this.l+1，否则如果this.l<last.r,并且this.r>last.r，就this.r-last.r（不加1因为last.r已经算过），如果this.r<last.r，则不必再计算。

看！代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+10;
struct node{
    int up,down;
    node(int x,int y){
        up=x;down=y;
    }
};
bool cmp(node a,node b)
{
    if(a.up==b.up) return a.down>b.down;
    return a.up<b.up;
}

int main()
{
    int t;
    int n,m,q;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,r,ux,dx,ly,ry;
        scanf("%d%d%d",&n,&m,&q);
        vector <node> v[MAXN*2];
        for(int i=0;i<q;i++)
        {
            scanf("%d%d%d",&x,&y,&r);
            ly=max(0,y-r);
            ry=min(y+r,m-1);
            for(int j=ly;j<=ry;j++) //先处理出每列对应的扫描线，存下来
            {
                int derta=sqrt(r*r-(y-j)*(y-j));
                ux=max(0,x-derta);
                dx=min(n-1,x+derta);
                v[j].push_back(node(ux,dx));
            }
        }
        int len;
        int last,ans=n*m;
        for(int i=0;i<m;i++) //对应每一列存在的扫描线，先从l小，r大排序，然后判断计算
        {
            len=v[i].size();
            if(len)
            {
                last=-1;
                sort(v[i].begin(),v[i].end(),cmp);
                for(int j=0;j<len;j++)
                {
                    if(v[i][j].down<=last)
                        continue;
                    if(v[i][j].up>last)
                        ans-=v[i][j].down-v[i][j].up+1;
                    else if(v[i][j].down>last)
                        ans-=v[i][j].down-last;
                    last=v[i][j].down;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;

}