二分+二分图
看到最大值最小，考虑二分。二分距离最大值，限制了某些点对不能分到同一组，明显的二分图模型。
用这些限制条件建图，跑二分图染色，看是否能分为二分图即可。
考虑方案数的计算，题目中方案数不同的要求是第一组的集合不同就为不同方案，所以跑完二分图后，图分为若干连通块，连通块中有若干黑点和白点，可以让黑点在第一组的集合也可以让白点在第一组，所以若连通块个数为 \(x\)，那么方案数就是 \(2^x\)。
复杂度 \(O(n^2\log n)\)。感觉一点跑不过去啊
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <bitset>
#include <string.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 10, mod = 1e9 + 7;
int n;
i64 ans, ans2, cnt;
int col[N];
struct node {int x, y;} a[N];
std::vector<int> e[N];
bool dfs(int u, int fa, int co) {
col[u] = co;
for(auto v : e[u]) {
if(v == fa) continue;
if(col[v] == -1) {
if(!dfs(v, u, co ^ 1)) return 0;
} else if(col[u] == col[v]) return 0;
}
return 1;
}
int dis(node a, node b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
bool check(int x) {
cnt = 0;
memset(col, -1, sizeof(col));
for(int i = 1; i <= n; i++) e[i].clear();
for(int u = 1; u <= n; u++) {
for(int v = u + 1; v <= n; v++) {
if(dis(a[u], a[v]) > x) e[u].pb(v), e[v].pb(u);
}
}
for(int i = 1; i <= n; i++) {
if(col[i] == -1) {
cnt++;
if(!dfs(i, 0, 0)) {
return 0;
}
}
}
ans2 = cnt;
return 1;
}
i64 qpow(i64 a, i64 b) {
i64 ret = 1;
while(b) {
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
void Solve() {
std::cin >> n;
for(int i = 1; i <= n; i++) {
std::cin >> a[i].x >> a[i].y;
}
int l = 0, r = 1e4;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
std::cout << ans << "\n" << qpow(2, ans2) << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}