fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. // Nhận xét: Với khoảng cách d càng lớn thì vị trí của d trong dãy sau khi sort càng lớn
  14. // => Tìm kiếm nhị phân khoảng cách d đầu tiên có vị trí >= k 
  15. // Vị trí của d = (Số cặp (i, j) sao cho dist(i, j) <= d), với dist(i, j) là khoảng cách giữa 2 ngôi nhà i, j
  16. // Nhận xét: dist(i, j) = max(|x(i) - x(j)|, |y(i) - y(j)|) hay còn gọi là khoảng cách Chebyshev
  17. // dist(i, j) <= d <=> max(|x(i) - x(j)|, |y(i) - y(j)|) <= d 
  18. //                 <=> |x(i) - x(j)| <= d và |y(i) - y(j)| <= d
  19. // Do đó để đơn giản hơn cho việc tính toán vị trí của d thì ta sẽ sort lại toạ độ của các ngôi nhà theo x
  20. // Khi xét đến ngôi nhà thứ i, ta sẽ đếm xem có bao nhiêu ngôi nhà j > i sao cho dist(i, j) <= d
  21. // Vì các ngôi nhà đã được sort lại theo x nên lúc này |x(i) - x(j)| = x(j) - x(i)
  22. // Để x(j) - x(i) <= d thì x(j) <= x(i) + d
  23. // Nên với mỗi i, cần tìm j xa nhất thoả mãn x(j) <= x(i) + d, tạm gọi là rj
  24. // Lúc này cần đếm xem có bao nhiêu chỉ số j thuộc [i + 1, rj] 
  25. // sao cho |y(i) - y(j)| <= d <=> y(j) thuộc đoạn [y(i) - d, y(i) + d]
  26. // => Có thể áp dụng kĩ thuật 2 con trỏ và duy trì thêm 1 CTDL như BIT trong quá trình duyệt 
  27. struct Point {
  28. 	int x, y;  
  29. 	bool operator<(const Point& other) const {
  30. 		return x < other.x; 
  31. 	}
  32. }; 
  33.  
  34. struct Fenwick {
  35. 	int n; 
  36. 	vector<int> ft;  
  37.  
  38. 	Fenwick(int n): n(n) {
  39. 		ft.resize(n, 0);  
  40. 	}
  41.  
  42. 	void update(int pos, int val) {
  43. 		for (; pos < n; pos = pos | (pos + 1)) ft[pos] += val; 
  44. 	}
  45.  
  46. 	int get(int pos) {
  47. 		int ans = 0;   
  48. 		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) ans += ft[pos]; 
  49. 		return ans;  
  50. 	}
  51. };
  52.  
  53. int n; ll k;  
  54. Point a[N];  
  55.  
  56. vector<int> vals; // Danh sách những giá trị cần nén
  57.  
  58. // Giá trị nén của x
  59. int getIdx(int x) { 
  60. 	return lower_bound(vals.begin(), vals.end(), x) - vals.begin();  
  61. }
  62.  
  63. bool check(ll d) {
  64. 	Fenwick fenw(vals.size());  
  65. 	ll pos = 0;   
  66. 	for (int i = 1, j = 0; i <= n; i++) {
  67. 		// j xa nhất thoả mãn a[j].x <= a[i].x + d
  68. 		while (j + 1 <= n && a[j + 1].x <= a[i].x + d) {
  69. 			j++; 
  70. 			int u = getIdx(a[j].y); 
  71. 			fenw.update(u, 1); 
  72. 		}
  73.  
  74. 		// Đếm số lượng j thoả mãn a[j].y thuộc đoạn [a[i].y - d, a[i].y + d]
  75. 		// Giá trị nén của phần tử lớn nhất < a[i].y - d
  76. 		int l = lower_bound(vals.begin(), vals.end(), a[i].y - d) - vals.begin() - 1; 
  77. 		// Giá trị nén của phần tử lớn nhất <= a[i].y + d
  78. 		int r = upper_bound(vals.begin(), vals.end(), a[i].y + d) - vals.begin() - 1; 
  79. 		pos += fenw.get(r) - fenw.get(l); 
  80. 		pos -= 1; // Trừ trường hợp j = i  
  81.  
  82. 		int u = getIdx(a[i].y); 
  83. 		fenw.update(u, -1); 
  84. 	}
  85. 	return (pos >= k);  
  86. }
  87.  
  88. int main() {
  89. 	ios::sync_with_stdio(false); 
  90. 	cin.tie(nullptr); 	
  91. 	cin >> n >> k; 
  92.  
  93. 	for (int i = 1; i <= n; i++) {
  94. 		cin >> a[i].x >> a[i].y;  
  95. 		vals.push_back(a[i].y);  
  96. 	}
  97.  
  98. 	sort(a + 1, a + n + 1);   
  99.  
  100. 	sort(vals.begin(), vals.end());  
  101. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());  
  102.  
  103. 	ll l = 0, r = 2e9, ans = -1;  
  104. 	while (l <= r) {
  105. 		ll mid = (l + r) >> 1; 
  106.  
  107. 		if (check(mid)) {
  108. 			ans = mid; 
  109. 			r = mid - 1; 
  110. 		}
  111. 		else {
  112. 			l = mid + 1; 
  113. 		}
  114. 	}
  115.  
  116. 	cout << ans << '\n'; 
  117. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
4 3
3 1
1 -1
0 5
-2 1
stdout
copy 
4
https://ideone.com/buRGQM
language:
C++14 (gcc 8.3)
created:
36 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!