かくさん
1267 ワード
答えは明らかに単調性を持っていて、二分答え、判断時に使用してセットを調べて維持することができて、2つの点が連通できる条件(|xi-xj|+|yi-yj|+1)/2<=mid)に注意します.
時間複雑度(O(nlogn*log_2 T)).
転載先:https://www.cnblogs.com/Maktub-blog/p/11443288.html
時間複雑度(O(nlogn*log_2 T)).
#include
#include
#include
#include
using namespace std;
#define FOR(a, b, c) for(int (a) = b; (a) <= (c); (a)++)
const int mx = 55;
struct node{
int x, y;
}a[mx];
int n;
int fat[mx];
inline void reset() { FOR(i, 1, n) fat[i] = i; }
inline int find(int x) { return x == fat[x] ? x : fat[x] = find(fat[x]); }
int dist(int i, int j) {
return (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) + 1)/2;
}
inline bool check(int x) {
reset();
FOR(i, 1, n-1)
FOR(j, i+1, n) {
if(dist(i, j) <= x) {
fat[find(i)] = find(j);
}
}
int cnt = 0;
FOR(i, 1, n) if(fat[i] == i) cnt++;
return cnt == 1;
}
int main() {
cin >> n;
FOR(i, 1, n) scanf("%d %d", &a[i].x, &a[i].y);
int l = 0, r = 1e9;
FOR(i, 1, 100) {
int mid = l + (r-l)/2;
if(check(mid)) r = mid;
else l = mid;
}
//mid~r , r, l
cout << r;
return 0;
}
転載先:https://www.cnblogs.com/Maktub-blog/p/11443288.html