Untitled

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> y;
vector<int> y_sort;
pair<int, int> mummy[100010];
map<int, int> y_map;

struct Range{
    int x, io; //mummy:in = 1, out = 0 me:in = 3, out = 2
    pair<int, int> y;
}m_range[200010];

struct Segment_tree{
    int x, la; //node值, lazy
    pair<int, int> seg; //segment
}tree[800000];

void init(int rou){
    for(int i = 0; i < n; i++){
        cin >> mummy[i].first >> mummy[i].second;
    }
}

//range的比較
bool compare(Range a, Range b){
    if(a.x <= b.x){
        if(a.x == b.x && a.io > b.io){
            return false;
        }
        return true;
    }
    else{
        return false;
    }
}

void create_tree(int L, int R, int node){
    tree[node].la = 0;
    tree[node].seg.first = L;
    tree[node].seg.second = R;
    tree[node].x = 0;
    int mid = (L + R) / 2;
    if(L != R){
        create_tree(L, mid, node * 2);
        create_tree(mid + 1, R, node * 2 + 1);
    }
}


int add_sub_segment(int l, int r, int value, int node){
    //node區間完全在想要的區間以內，不需再往下做
    if(tree[node].seg.first >= l && tree[node].seg.second <= r){
        tree[node].x = tree[node].x + value;
        tree[node].la = tree[node].la + value;
        return tree[node].x;
    }
    //把lazy值往下做
    tree[node * 2].x += tree[node].la;
    tree[node * 2 + 1].x += tree[node].la;
    tree[node * 2].la += tree[node].la;
    tree[node * 2 + 1].la += tree[node].la;
    tree[node].la = 0;
    int mid = (tree[node].seg.first + tree[node].seg.second) / 2;
    //左右子樹都做
    if(l <= mid && r > mid){
        tree[node].x = min(add_sub_segment(l, mid, value, node * 2), add_sub_segment(mid + 1, r, value, node * 2 + 1));
    }
    //右子樹
    if(l > mid && r >= l){
        tree[node].x = min(tree[node * 2].x ,add_sub_segment(l, r, value, node * 2 + 1));
    }
    //左子樹
    if(l <= r && r <= mid){
        tree[node].x = min(add_sub_segment(l, r, value, node * 2), tree[node * 2 + 1].x);
    }
    return tree[node].x;
}

int search_segment_tree(int l, int r, int node, int save){
    if(tree[node].seg.first >= l && tree[node].seg.second <= r){
        if(tree[node].x <= 0){
            save++;
            //cout << node << " node\n";
        }
        return save;
    }
    tree[node * 2].x += tree[node].la;
    tree[node * 2 + 1].x += tree[node].la;
    tree[node * 2].la += tree[node].la;
    tree[node * 2 + 1].la += tree[node].la;
    tree[node].la = 0;
    int mid = (tree[node].seg.first + tree[node].seg.second) / 2;
    if(l <= mid && r > mid){
        save += search_segment_tree(l, mid, node * 2, save);
        save += search_segment_tree(mid + 1, r, node * 2 + 1, save);
        return save;
    }
    if(l > mid && r >= l){
        save += search_segment_tree(l, r, node * 2 + 1, save);
        return save;
    }
    if(l <= r && r <= mid){
        save += search_segment_tree(l, r, node * 2, save);
        return save;
    }
}

//判斷在len步數下會不會被抓到
int check(int len){
    int TF = 0;
    int l = 0;
    int r = 0;
    int ok = 0;
    y.clear();
    y_sort.clear();
    y_map.clear();
    m_range[0].x = -len;
    m_range[0].y.first = -len;
    m_range[0].y.second = len + 1;
    m_range[0].io = 3;
    m_range[1].x = len + 1;
    m_range[1].y.first = -len;
    m_range[1].y.second = len + 1;
    m_range[1].io = 2;
    for(int i = 1; i <= n; i++){
        m_range[2 * i].x = mummy[i - 1].first - len;
        m_range[2 * i].y.first = mummy[i - 1].second - len;
        m_range[2 * i].y.second = mummy[i - 1].second + len + 1;
        m_range[2 * i].io = 1;
        m_range[2 * i + 1].x = mummy[i - 1].first + len + 1;
        m_range[2 * i + 1].y.first = mummy[i - 1].second - len;
        m_range[2 * i + 1].y.second = mummy[i - 1].second + len + 1;
        m_range[2 * i + 1].io = 0;
    }
    sort(m_range, m_range + (2 * (n + 1)), compare);
    for(int i = 0; i < 2 * (n + 1); i ++){
        y.push_back(m_range[i].y.first);
        y.push_back(m_range[i].y.second);
    }
    sort(y.begin(), y.end());
    int temp = 1e9;
    for(int i = 0; i < y.size(); i++){
        if(temp != y[i]){
            y_sort.push_back(y[i]);
            y_map[y[i]] = y_sort.size();
            temp = y[i];
        }
    }
    //cout << y_sort.size() << " size\n";
    create_tree(1, y_sort.size(), 1);
    /*/
    for(int i = 0; i < 10; i++){
        cout << m_range[i].io << " " << m_range[i].x << " " << m_range[i].y.first << " " << m_range[i].y.second << " in/out x y1 y2\n";
    }
    //*/
    for(int i = 0; i < 2 * (n + 1); i++){
        if(m_range[i].io == 0){
            add_sub_segment(y_map[m_range[i].y.first], y_map[m_range[i].y.second] - 1, -1, 1);
            /*/
            cout << y_map[m_range[i].y.first] << " " << y_map[m_range[i].y.second] - 1 << " >> ";
            for(int j = 1; j <= 33; j++){
                cout << tree[j].x << " " << j << " " << tree[j].la <<  " / ";
            }
            //*/
        }
        if(m_range[i].io == 1){
            add_sub_segment(y_map[m_range[i].y.first], y_map[m_range[i].y.second] - 1, 1, 1);
            /*/
            cout << y_map[m_range[i].y.first] << " " << y_map[m_range[i].y.second] - 1 << " >> ";
            for(int j = 1; j <= 33; j++){
                cout << tree[j].x << " " << j << " " << tree[j].la <<  " / ";
            }
            //*/
        }
        if(m_range[i].io == 2){
            TF = 0;
            /*/
            cout << y_map[m_range[i].y.first] << " " << y_map[m_range[i].y.second] - 1 << " >> ";
            for(int j = 1; j <= 33; j++){
                cout << tree[j].x << " " << j << " " << tree[j].la <<  " / ";
            }
            //*/
        }
        if(m_range[i].io == 3){
            TF = 1;
            l = y_map[m_range[i].y.first];
            r = y_map[m_range[i].y.second] - 1;
            /*/
            cout << y_map[m_range[i].y.first] << " " << y_map[m_range[i].y.second] - 1 << " >> ";
            for(int j = 1; j <= 33; j++){
                cout << tree[j].x << " " << j << " " << tree[j].la << " / ";
            }
            //*/
        }
        if(TF == 1){
            if(search_segment_tree(l, r, 1, 0) > 0){
                ok ++;
            }
            /*/
            cout << "\n" << ok << " " << l << " " << r << " ok l r\n";
            for(int j = 1; j <= 1; j++){
                cout << tree[j].x << " " << j << " " << tree[j].la <<  " TF/ ";
            }
            //*/
        }
        //cout << "\n";
    }
    //cout << ok << " ok\n";
    return ok;
}

//二分搜可以逃的步數
int b_search(int l, int r){
    while(l < r && l < 1000005){
        int mid = (l + r) / 2;
        //cout << mid << " " << l << " " << r << " mid l r\n"; 
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    return l;
}

void solve(int rou){
    int ans;
    init(rou);
    ans = b_search(1, 1000010);
    //check(8);
    if(ans >= 1000005){
        cout << "Case " << rou << ": never\n"; 
    }
    else{
        cout << "Case " << rou << ": " << ans << "\n"; 
    }
}

int main(){
    int rou = 1;
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    while(cin >> n && n != -1){
        solve(rou++);
    }
}