Advertisement
BaoJIaoPisu

Untitled

Dec 23rd, 2021
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define pf push_front
  17. #define mp make_pair
  18. #define ins insert
  19.  
  20. #define sz(x) (int)(x.size());
  21. #define all(x) x.begin(), x.end()
  22. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  23.  
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  27. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  28. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  29.  
  30. template<class X, class Y>
  31.     bool minimize(X &x, const Y &y) {
  32.         if (x > y)
  33.         {
  34.             x = y;
  35.             return true;
  36.         }
  37.         return false;
  38.     }
  39. template<class X, class Y>
  40.     bool maximize(X &x, const Y &y) {
  41.         if (x < y)
  42.         {
  43.             x = y;
  44.             return true;
  45.         }
  46.         return false;
  47.     }
  48.  
  49. const int MOD = 1e9 + 7; //998244353
  50.  
  51. template<class X, class Y>
  52.     void add(X &x, const Y &y) {
  53.         x = (x + y);
  54.         if(x >= MOD) x -= MOD;
  55.     }
  56.  
  57. template<class X, class Y>
  58.     void sub(X &x, const Y &y) {
  59.         x = (x - y);
  60.         if(x < 0) x += MOD;
  61.     }
  62.  
  63. /* Author : Le Ngoc Bao Anh, 11A5, LQD High School for Gifted Student*/
  64.  
  65. const ll INF = 1e9;
  66. const int N = 8005 + 10;
  67.  
  68. int par[N];
  69. ll x[N], y[N];
  70.  
  71. struct Edges {
  72.     int u, v, w;
  73. } ed[N * N / 2];
  74.  
  75. int find_par(int u) {
  76.     if(par[u] < 0) return u;
  77.     par[u] = find_par(par[u]);
  78.     return par[u];
  79. }
  80. void solve() {
  81.     int n; ll h;
  82.     cin >> n >> h;
  83.     for(int i = 1; i <= n; i++) {
  84.         cin >> x[i] >> y[i];
  85.     }
  86.  
  87.     int cnt = 0;
  88.     for(int i = 1; i <= n; i++) {
  89.         ed[++cnt] = {0, i, (int)y[i]};
  90.         ed[++cnt] = {n + 1, i, (int)(h - y[i])};
  91.         for(int j = i + 1; j <= n; j++) {
  92.             ed[++cnt] = {i, j, (int)sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))};
  93.         }
  94.     }
  95.  
  96.     for(int i = 0; i <= n + 1; i++) par[i] = -1;
  97.     auto merge = [&](int u, int v) -> void {
  98.         u = find_par(u), v = find_par(v);
  99.         if(u == v) return;
  100.         if(par[u] > par[v]) swap(u, v);
  101.         par[u] += par[v];
  102.         par[v] = u;
  103.     }; 
  104.  
  105.     auto ok = [&](int dist) -> bool {
  106.         for(int i = 0; i <= n + 1; i++) par[i] = -1;
  107.         for(int i = 1; i <= cnt; i++) {
  108.             if(ed[i].w <= dist) {
  109.                 merge(ed[i].u, ed[i].v);
  110.                 if(find_par(0) == find_par(n + 1)) return false;
  111.             }
  112.         }
  113.  
  114.         return true;
  115.     };
  116.  
  117.     int L = 1, R = 1e9, ans = 1;
  118.     while(L <= R) {
  119.         int mid = (L + R) >> 1;
  120.         if(ok(mid)) {
  121.             ans = mid + 1;
  122.             L = mid + 1;
  123.         } else R = mid - 1;
  124.     }
  125.  
  126.     cout << ans;
  127. }
  128.  
  129. int main()
  130. {
  131.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  132.     #ifndef ONLINE_JUDGE
  133.     freopen("input.txt", "r", stdin);
  134.     freopen("output.txt", "w", stdout);
  135.     #else
  136.     //online
  137.     #endif
  138.  
  139.     int tc = 1, ddd = 0;
  140.     // cin >> tc;
  141.     while(tc--) {
  142.         //ddd++;
  143.         //cout << "Case #" << ddd << ": ";
  144.         solve();
  145.     }
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement