AtCoder Beginner Contest 215 F - Dist Max 2

平面上有一系列的點$(x_i,y_i)$，定義兩點$(x_i,y_i),(x_j,y_j)$的距離為$min(|x_i?x_j|,|y_i?y_j|)$，求出最遠的兩個點的距離

想過用二分答案，但是沒有想到怎么check，賽后看到題解發現其實很簡單。

首先還是二分答案，要找到一個點對使兩個元素的差值都要大于等于這個答案。所以，首先先對x坐標進行排序，那么點對的范圍就可以容易找到，比如對于$x_1$有著$x_{k?1}<x_1+ans$并且$x_k>=x_1+ans$，那么k到n的點對就滿足了x方向的條件。這個時候，我們維護一個后綴的最大值和最小值，$O(1)$查找k~n的y方向的最大值和最小值，和$y_1$進行比較，如果存在滿足要求的，那么ans就是可行的；如果不滿足，就求$x_2$，這樣滑動窗口求下去。

#include <bits/stdc++.h> #define f(i, n) for(int i = 1; i <= n; i ++) #define nf(i, n) for(int i = n; i >= 1; i --) typedef long long ll; using namespace std;const int N = 2e5 + 10;struct node {int x, y; }; node a[N];int mx[N], mn[N];bool cmp(const node &a, const node &b) {return a.x < b.x; }int n;bool check(int x) {int p = 1, q = 1;while (p <= n && q <= n){while (a[q].x - a[p].x < x && q <= n)++ q;if (q > n)return false;if (a[p].y - mn[q] >= x || mx[q] - a[p].y >= x)return true;++ p; }return false; }int main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T --){cin >> n;f(i, n)cin >> a[i].x >> a[i].y;sort (a + 1, a + n + 1, cmp);mx[n] = mn[n] = a[n].y;nf(i, n - 1){mx[i] = max(mx[i + 1], a[i].y);mn[i] = min(mn[i + 1], a[i].y);}int l = 0, r = 1e9, mid, ans;while (l <= r){mid = (l + r) >> 1;if (check(mid)){ans = mid;l = mid + 1;}elser = mid - 1;}cout << ans;}return 0; }

總結

以上是生活随笔為你收集整理的AtCoder Beginner Contest 215 F - Dist Max 2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。