# Mất kết nối
Tác giả : Vũ Phương (☞ﾟヮﾟ)☞
## Tóm tắt đề :
Bảo đẹp trai nghe tin có một khu đô thị gồm $n$ ngôi nhà, mỗi ngôi nhà thứ $i$ nằm ở tọa độ $a_i$, và trên đường thẳng đó có $m$ tháp điện mỗi tháp điện thứ $i$ nằm ở tọa độ $b_i$.

### Yêu cầu:
* Tìm cường độ phát điện nhỏ nhất $x$ sao cho tất cả $n$ ngôi nhà đều nhận được điện từ ít nhất một tháp.
* Một ngôi nhà $a_i$ sẽ nhận được điện từ tháp $b_j$ nếu $|a_i − b_j| \leq x$

### Subtask
- Subtask 1 : $n, m \leq 1000$
- Subtask 2 : $n, m \leq 10^4$ và $x \leq 10^3$
- Subtask 3 : Không có ràng buộc gì thêm.

## Subtask 1 : $n, m \leq 1000$
### Thuật toán
- Ta chỉ cần đơn giản duyệt qua từng ngôi nhà thứ $i$ tìm tháp điện $j$ sao cho $|a_i - b_j|$ nhỏ nhất. Kết quả chính là max giá trị để kết nối của mỗi ngôi nhà.

### Độ phức tạp:
- Duyệt từng ngôi nhà và tháp điện $O(n * m)$.
### Code C++:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int maxn = 1e6 + 5;
int a[maxn], b[maxn], n, m;

main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("ketnoi.inp", "r", stdin);
    freopen("ketnoi.out", "w", stdout);
    int test = 1;
    cin >> test;
    while(test--) {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) cin >> a[i];
    	for (int i = 1; i <= m; i++) cin >> b[i];
    	int maxi = 0;
    	for (int i = 1; i <= n; i++) {
    		int mini = 1e18;
    		for (int j = 1; j <= m; j++) {
    			mini = min(mini, abs(a[i] - b[j]));
    		}
    		maxi = max(maxi, mini);
    	}
    	cout << maxi << endl;
    }
}

---

## Subtask 2 : $n, m \leq 10^4$ và $x \leq 10^3$

### Thuật toán:
- Vì giá trị cường độ điện $x$ được giới hạn, ta chỉ cần dùng 1 vòng for cố định giá trị $x$, và dùng thuật toán 2 con trỏ để kiểm tra xem cường độ $x$ có thỏa mãn hay không.

### Độ phức tạp:
- Cố định giá trị $x$ và dùng 2 con trỏ để kiểm tra $O(10^3 * (n + m))$

---

### Code C++:

const int maxn = 1e6 + 5;
int a[maxn], b[maxn], n, m;
bool check(int x) {
	int j = 1;
	for (int i = 1; i <= n; i++) {
		while(j <= m && b[j] < a[i] - x) {
			j++;
		}
		if (j <= m && abs(b[j] - a[i]) <= x) continue;
		return false;
	}
	return true;
}
main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("ketnoi.inp", "r", stdin);
    freopen("ketnoi.out", "w", stdout);
    int test = 1;
    cin >> test;
    while(test--) {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) cin >> a[i];
    	for (int i = 1; i <= m; i++) cin >> b[i];
    	sort(a+1,a+n+1);
    	sort(b+1,b+m+1);
    	for (int x = 0; x <= 1000; x++) {
    		if (check(x)) {
    			cout << x << endl;
    			break;
    		}
    	}
    }
}

---

## Subtask 3 : Không có ràng buộc gì thêm.

### Thuật toán:
- Khi giải được subtask 2 thì subtask 3 cũng không quá khó để cải tiến, thay vì dùng 1 for để cố định giá trị $x$, ta chặt nhị phân giá trị $x$ và tiếp tục dùng 2 con trỏ để kiểm tra giá trị $x$ có thỏa mãn hay không.

### Độ phức tạp:
- Chặt nhị phân đáp án và sử dụng 2 con trỏ để kiểm tra $O((n + m)*log(10^9))$

---

### Code C++:

const int maxn = 1e6 + 5;
int a[maxn], b[maxn], n, m;
bool check(int x) {
	int j = 1;
	for (int i = 1; i <= n; i++) {
		while(j <= m && b[j] < a[i] - x) {
			j++;
		}
		if (j <= m && abs(b[j] - a[i]) <= x) continue;
		return false;
	}
	return true;
}
main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("ketnoi.inp", "r", stdin);
    freopen("ketnoi.out", "w", stdout);
    int test = 1;
    cin >> test;
    while(test--) {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) cin >> a[i];
    	for (int i = 1; i <= m; i++) cin >> b[i];
    	sort(a+1,a+n+1);
    	sort(b+1,b+m+1);
    	int l = 0, r = 1e12, res = 0;
    	while(l <= r) {
    		int mid = (l + r)/2;
    		if (check(mid)) {
    			res = mid;
    			r = mid - 1;
    		}
    		else l = mid + 1;
    	}
    	cout << res << endl;
    }
}