Topic Description

Portal

Topic: A square grid, you and the mummy take turns to move (you take the first step). When it's your turn, you can move to one of the eight adjacent grids or stand still. When it's mummy's turn, each mummy moves to one of its adjacent lattices, making it as close as possible to your Euclidean distance (assuming you and the mummy are at the center of the lattice). Multiple mummies are allowed to occupy the same grid at the same time.
In each unit of time, you move first, and then the mummy moves. If you are in the same position as any mummy, you will be caught. Of course, you try to avoid being caught for as long as possible. How many units of time will you be caught?

Title Solution

Firstly, we divide the answer into two parts. Then we mark H and the point that each mummy can reach in this time. We can find that it is n+1 square. The condition that is not caught is that the square determined by H is not a union subset of the square determined by all mummies.
Scanning line is used to solve the problem. First, the longitudinal coordinates are discretized, then the mummy's square is decomposed into left and right lines, and then sorted according to the abscissa. Every time a line segment is added or subtracted in the range, and then every time we judge whether it is completely covered, we should pay attention to the order of addition, statistical answer and subtraction.
But there are some special boundary conditions that need to be judged: if there is a column that can not be skipped without operation, it should also be judged; the left and right boundaries of H should be judged; if there is an empty behavior, a line should be added to it when discretization occurs.

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 100005

int T,n,Max,Min,LSH,cnt,ans;
struct P{int x,y;}p[N];
struct LINE{int x,l,r,val;}line[N<<1];
int lsh[400004],cover[1000005],sum[1000005];

void clear()
{
    Max=Min=LSH=cnt=ans=0;
    memset(lsh,0,sizeof(lsh));
}
int cmp(LINE a,LINE b)
{
    return a.x<b.x||(a.x==b.x&&a.val>b.val);
}
void update(int now,int l,int r)
{
    if (cover[now]) sum[now]=r-l+1;
    else if (l==r) sum[now]=0;
    else sum[now]=sum[now<<1]+sum[now<<1|1];
}
void change(int now,int l,int r,int lr,int rr,int v)
{
    if (lr>rr) return;
    int mid=(l+r)>>1;
    if (lr<=l&&r<=rr)
    {
        cover[now]+=v;
        update(now,l,r);
        return;
    }
    if (lr<=mid) change(now<<1,l,mid,lr,rr,v);
    if (mid+1<=rr) change(now<<1|1,mid+1,r,lr,rr,v);
    update(now,l,r);
}
bool check(int mid)
{
    LSH=cnt=0;memset(lsh,0,sizeof(lsh));
    for (int i=1;i<=n;++i)
    {
        if (p[i].x+mid<-mid||p[i].x-mid>mid) continue;
        if (p[i].y+mid<-mid||p[i].y-mid>mid) continue;
        int ll=max(p[i].y-mid,-mid),rr=min(p[i].y+mid,mid);
        lsh[++LSH]=ll,lsh[++LSH]=rr;
        line[++cnt].x=max(p[i].x-mid,-mid),line[cnt].l=ll,line[cnt].r=rr,line[cnt].val=1;
        line[++cnt].x=min(p[i].x+mid,mid),line[cnt].l=ll,line[cnt].r=rr,line[cnt].val=-1;
    }
    lsh[++LSH]=-mid,lsh[++LSH]=mid;
    sort(lsh+1,lsh+LSH+1);LSH=unique(lsh+1,lsh+LSH+1)-lsh-1;
    int now=LSH;
    for (int i=2;i<=now;++i)
        if (lsh[i]>lsh[i-1]+1) lsh[++LSH]=lsh[i]-1;
    sort(lsh+1,lsh+LSH+1);LSH=unique(lsh+1,lsh+LSH+1)-lsh-1;
    int l=lower_bound(lsh+1,lsh+LSH+1,-mid)-lsh;
    int r=lower_bound(lsh+1,lsh+LSH+1,mid)-lsh;
    sort(line+1,line+cnt+1,cmp);
    for (int i=1;i<=cnt;++i)
    {
        line[i].l=lower_bound(lsh+1,lsh+LSH+1,line[i].l)-lsh;
        line[i].r=lower_bound(lsh+1,lsh+LSH+1,line[i].r)-lsh;
    }
    if (line[1].x>-mid) return 1;
    if (line[cnt].x<mid) return 1;
    memset(sum,0,sizeof(sum));
    memset(cover,0,sizeof(cover));
    for (int i=1,j;i<=cnt;i=j)
    {
        if (i>1&&line[i].x>line[i-1].x+1)
        {
            if (sum[1]<r-l+1) return 1;
        }
        j=i;
        while (j<=cnt&&line[j].x==line[i].x&&line[j].val==1)
        {
            int lr=line[j].l-l+1,rr=line[j].r-l+1;
            change(1,1,r-l+1,lr,rr,1);
            ++j;
        }
        if (sum[1]<r-l+1) return 1;
        while (j<=cnt&&line[j].x==line[i].x&&line[j].val==-1)
        {
            int lr=line[j].l-l+1,rr=line[j].r-l+1;
            change(1,1,r-l+1,lr,rr,-1);
            ++j;
        }
    }
    return 0;
}
int find()
{
    int l=1,r=Max-Min+1,mid;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main()
{
    while (~scanf("%d",&n))
    {
        if (n==-1) break;
        clear();
        for (int i=1;i<=n;++i)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            Min=min(Min,p[i].x),Min=min(Min,p[i].y);
            Max=max(Max,p[i].x),Max=max(Max,p[i].y);
        }
        ans=find()+1;
        if (ans>Max-Min) printf("Case %d: never\n",++T);
        else printf("Case %d: %d\n",++T,ans);
    }
}