NOIp模拟赛 富 题解【扫描线】【线段树】

点击量：177

    扫描线加强版，求周长，有点类似IOI1998 picture。

目录

题目描述

富先生所在的地方是一个\(n\times m\)的网格，苟先生排出了他的狼狗大军，共有\(k\)条狗，第\(i\)条狗所在的位置为\((x_i, y_i)\)。每条狗每个时刻都可以向\(8\)个方向前进一步。

 

如果一个格子最快的一条狗需要\(t\)时刻才能到，那么这个格子就是\(t\)-危险的，现在给你\(t\)，询问有多少个\(t\)-危险的格子。

 

输入输出格式

输入格式：

第一行四个整数\(n,m,k,t\)。

 

接下来\(k\)行每行两个整数\(x_i,y_i\)，没有两条狗在同一个位置。

 

输出格式：

一行一个整数表示答案。

 

输入输出样例

输入样例#1：

5 6 2 2
3 3
2 4

输出样例#1：

15

说明

对于\(30\%\)的数据\(n,m\le 1000\)；

 

对于另外\(20\%\)的数据\(k\le 50,n\le 1000\)；

 

对于另外\(20\%\)的数据\(k\le 50\)；

 

对于\(100\%\)的数据\(k\le 2000, n, m\le 1000000000, t\le n+m\)。

题解：

    首先乍一看，好像是在求一些宽为1的矩形的面积并，可以稍微推一下，但是情况复杂了会发现没有通式可以推。因此可以把这种类似周长的东西看作是一个\(n\times n\)的正方形面积减去\((n-1)\times (n-1)\)的面积。

    手画可以发现，当出现面积并的时候，\(n\times n\)的正方形面积并减去\((n-2)\times (n-2)\)的面积并，就是这些正方形并的周长。因为周长上的点距离题目中的“狗”，距离总是\(\frac n2\)。因此求出“周长”就可以用上述的大正方形面积并减去小正方形面积并。

    这个题需要注意一点，因为这里的面积是从整个格子开始算，而不是格子的边缘，如果习惯按格子的边缘算就要把右边缘和下边缘都扩展1。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
using std::sort;
using std::map;
using std::max;
using std::min;
struct line
{
    int x,up,down,v;
    line(int x,int up,int down,int v)
    {
        this->x=x;
        this->up=up;
        this->down=down;
        this->v=v;
    }
    line(){}
    friend bool operator <(line a,line b)
    {
        return a.x<b.x;
    }
}b[5000];
int a[5000];
struct node
{
    int l,r,num;
    long long v;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        num=0,v=0;
    }
    node(){}
}t[16000];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
    return;
}
void change(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].num+=x;
        if(t[k].num)
            t[k].v=a[r+1]-a[l];
        else if(l<r)
            t[k].v=t[ls].v+t[rs].v;
        else
            t[k].v=0;
        return;
    }
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    if(t[k].num)
        t[k].v=a[t[k].r+1]-a[t[k].l];
    else
        t[k].v=t[ls].v+t[rs].v;
    return;
}
int x[2010],y[2010];
int k,N,M;
map<int,int> m;
long long area(int T)
{
    build(1,1,2*k);
    if(!T)
        return k;
    for(int i=1;i<=k;++i)
    {
        b[(i<<1)-1]=line(max(1,y[i]-T),min(N,x[i]+T)+1,max(1,x[i]-T),1);
        b[i<<1]=line(min(M,y[i]+T)+1,b[(i<<1)-1].up,b[(i<<1)-1].down,-1);
        a[(i<<1)-1]=b[i<<1].up;
        a[i<<1]=b[i<<1].down;
    }
    std::sort(a+1,a+1+2*k);
    for(int i=1;i<=2*k;++i)
        m[a[i]]=i;
    std::sort(b+1,b+1+2*k);
    long long ans=0;
    for(int i=1;i<2*k;++i)
    {
        change(1,m[b[i].down],m[b[i].up]-1,b[i].v);
        ans+=(long long)t[1].v*(b[i+1].x-b[i].x);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d%d%d%d",&N,&M,&k,&t);
    for(int i=1;i<=k;++i)
        scanf("%d%d",&x[i],&y[i]);
    printf("%lld\n",area(t)-area(t-1));
    return 0;
}