# Untitled

unknown
plain_text
a year ago
7.6 kB
1
Indexable
Never
```#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++);
}
}```