forked from tmwilliamlin168/CompetitiveProgramming
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path18-3-A.java
More file actions
59 lines (55 loc) · 1.63 KB
/
18-3-A.java
File metadata and controls
59 lines (55 loc) · 1.63 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
- Binary search by number of steps
- The set of cells in which a person can walk to given a fixed number of steps forms a square
- Check that the intersection of the squares is non-empty
- It's intuitive but hard to prove that if the intersection is non-empty, all the people can actually meet there using the algorithm described in the problem
- This is actually the same as finding the minimum bounding square, which can be done in O(n) instead
*/
import java.io.*;
import java.util.*;
public class Solution {
static final Reader in = new Reader();
static final PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) {
int tt=in.nextInt();
for(int ti=1; ti<=tt; ++ti) {
int n=in.nextInt();
int[] r = new int[n], c = new int[n];
for(int i=0; i<n; ++i) {
r[i]=in.nextInt();
c[i]=in.nextInt();
}
int lb=0, rb=(int)5e8;
while(lb<=rb) {
int mb=(lb+rb)/2, lr=Integer.MIN_VALUE, rr=Integer.MAX_VALUE, lc=Integer.MIN_VALUE, rc=Integer.MAX_VALUE;
for(int i=0; i<n; ++i) {
lr=Math.max(r[i]-mb, lr);
rr=Math.min(r[i]+mb, rr);
lc=Math.max(c[i]-mb, lc);
rc=Math.min(c[i]+mb, rc);
}
if(lr<=rr&&lc<=rc)
rb=mb-1;
else
lb=mb+1;
}
out.println("Case #"+ti+": "+lb);
}
out.close();
}
static class Reader {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String next() {
while(st==null||!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch(Exception e) {}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}