fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-12-09 14:08:21
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-12-09 15:05:27
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define lb long double
  19. #define ll long long 
  20. #define ull unsigned long long
  21. #define sz(x) x.size()
  22. #define sqr(x) (1LL * (x) * (x))
  23. #define all(x) x.begin(), x.end()
  24. #define fill(f,x) memset(f,x,sizeof(f))
  25. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  26. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  27. #define debug(x) cout << #x << " = " << x << '\n'
  28. #define ii pair<int,int>
  29. #define iii pair<int,ii>
  30. #define di pair<ii,ii>
  31. #define vi vector<int>
  32. #define vii vector<ii>
  33. #define mii map<int,int>
  34. #define fi first
  35. #define se second
  36. #define pb push_back
  37. #define MOD 1000000007
  38. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  39. #define YES cout << "YES\n"
  40. #define NO cout << "NO\n"
  41. #define MASK(i) (1LL << (i))
  42. #define c_bit(i) __builtin_popcountll(i)
  43. #define BIT(x,i) ((x) & MASK(i))
  44. #define SET_ON(x,i) ((x) | MASK(i))
  45. #define SET_OFF(x,i) ((x) & ~MASK(i))
  46. #define oo 1e18
  47. #define name "SWOOP"
  48. #define endl '\n'
  49. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  50. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  51. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  52. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  53. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  54. const int N = (int)1e5+10;
  55. int n;
  56.  
  57. struct Point {
  58.     int x,y;
  59.     void input() {
  60.         cin >> x >> y;
  61.     }
  62. } a[N];
  63.  
  64. namespace hungeazy {
  65.  
  66.     bool can[N];
  67.  
  68.     lb dist(int i, int j) {
  69.         return sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));
  70.     }
  71.  
  72.     bool check(lb mid)
  73.     {
  74.         FOR(i,1,n) can[i] = false;
  75.         can[1] = true;
  76.         stack<int> st;
  77.         st.push(1);
  78.         FOR(i,2,n)
  79.         {
  80.             while (!st.empty() and a[st.top()].y <= a[i].y)
  81.             {
  82.                 can[i] |= (can[st.top()] and dist(st.top(),i) <= mid);
  83.                 st.pop();
  84.             }
  85.             if (!st.empty()) can[i] |= (can[st.top()] and dist(st.top(),i) <= mid);
  86.             st.push(i);
  87.         }
  88.         return can[n];
  89.     }
  90.  
  91. 	void solve(void)
  92. 	{
  93.         lb l = 0, r = 1e18, ans = 0;
  94.         FOR(rep,0,100)
  95.         {
  96.             lb mid = (l+r)/2.0;
  97.             if (check(mid)) ans = mid, r = mid-1;
  98.             else l = mid+1;
  99.         }    
  100.         cout << fixed << setprecision(10) << ans;
  101. 	}
  102.  
  103. }
  104.  
  105. bool M2;
  106. signed main()
  107. {
  108.     fast;
  109.     if (fopen(name".inp","r"))
  110.     {
  111.     	freopen(name".inp","r",stdin);
  112.     	freopen(name".out","w",stdout);
  113.     }
  114.     cin >> n;
  115.     FOR(i,1,n) a[i].input();
  116.     hungeazy::solve();
  117.     time();
  118.     memory();
  119.     return 0;
  120. }
  121. // ██░ ██  █    ██  ███▄    █   ▄████
  122. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  123. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  124. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  125. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  126. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  127. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  128. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  129. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000
stderr
copy 
-------------Time:7.317ms.
1.62147 MB
https://ideone.com/lVkyeN
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

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!