Submission #1243118

#TimeUsernameProblemLanguageResultExecution timeMemory
1243118neverspotMobile (BOI12_mobile)C++20
0 / 100
1078 ms16100 KiB
/* "If I can run I will run , If I can walk I will walk , If I can crawl I will crawl" */
/*                           " But I will NEVER_STOP "                                 */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
using namespace std;
using namespace __gnu_pbds;
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define NeverSpot cout.tie(NULL);
#define int long long
#define double long double
#define f first
#define s second
#define ed <<"\n";
#define co cout<<
#define ci cin>>
#define sped <<" ";
#define sp <<" "<<
#define love cout<<" Insha " ed
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define all(x) (x).begin(),(x).end()
#define fl(a,b) for (int i=a;i<(b);++i)
#define rfl(a,b) for (int i=a;i>=(b);--i)
#define sl(a,b) for (int j=a;j<(b);++j)
#define rsl(a,b) for (int j=a;j>=(b);--j)
#define tl(a,b) for (int k=a;k<(b);++k)
#define rtl(a,b) for (int k=a;k>=(b);--k)
#define test(t) int t;cin>>t;for(int O=1;O<=t;O++)
#define sortv(v) sort(all(v));
#define sumv(arr) accumulate(all(arr),0LL)
#define rev(v) reverse(all(v));
#define ai(o,size) vi o;fl(0,size){int p ; cin>>p ; (o).push_back(p);}
#define Mod 1000000007ll
#define Emod 998244353ll
#define inf 1000000000000000009ll
#define gcd __gcd
inline int Sqrt(int x){ int y=static_cast<long long>(sqrt(x))+5;while(y*y>x)y--;return y;}
#define log2(x) (64 - __builtin_clzll(x) - 1) // log2 in O(1) time
using mii = map<long long, long long>;
using vi = vector<long long>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<long long>>;
using vvp = vector<vector<pair<long long, long long>>>;
using pii = pair<long long, long long>;
using vp = vector<pair<long long, long long>>;
// typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_set; // find_by_order, order_of_key
// typedef tree<pair<int,int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_multiset; // find_by_order, order_of_key
// namespace std {
//   // fast swap
//   void swap(order_set &a, order_set &b) { a.swap(b); }
//   void swap(order_multiset &a, order_multiset &b) { a.swap(b); }
// }
string al="abcdefghijklmnopqrstuvwxyz";

//.........For Taking Mod............//
inline int power(int a, int b, int mod=Mod) {int res = 1; while (b > 0) {if (b & 1)res = res * a % mod; a = a * a % mod; b = b >> 1;} return res;}
class mod
{
  static int mminvprime(int a, int b) {return power(a, b - 2, b);}
public:
  int m=Mod;
  void set(int m) {this->m=m;}
  int add(int a, int b) {a = a % m; b = b % m; return ((a + b) % m + m) % m;}
  int mul(int a, int b) {a = a % m; b = b % m; return (a * b % m + m) % m;}
  int sub(int a, int b) {a = a % m; b = b % m; return ((a - b) % m + m) % m;}
  int div(int a, int b) {a = a % m; b = b % m; return (mul(a, mminvprime(b, m)) + m) % m;}  //only for prime m
}mod;

//.........Bit_Manipulation...........//
#define msb(mask) (63-__builtin_clzll(mask))  /// 0 -> -1
#define lsb(mask) __builtin_ctzll(mask)  /// 0 -> 64
#define cntsetbit(mask) __builtin_popcountll(mask)
#define checkbit(mask,bit) ((mask >> bit) & 1ll)
#define onbit(mask,bit) ((mask)|(1LL<<(bit)))
#define offbit(mask,bit) ((mask)&~(1LL<<(bit)))
#define changebit(mask,bit) ((mask)^(1LL<<bit))

// random number generator #BESTEST_QUAILTY :)
mt19937_64 gen(random_device{}());
long long rng(int l=0,int r=INT64_MAX){uniform_int_distribution<int> dist(l, r);return dist(gen);}

// Custom hashing for unordered map or set
const int RANDOM = rng();
struct chash{int operator()(int x) const { return x ^ RANDOM; }};

// Function
#define Ceil(a,b) ((a+b-1)/b)
#define print(arr) for(auto &o:(arr)){co o sped;} cout ed
#define mxe(v)  *max_element(v.begin(),v.end())     // find max element in vector
#define mne(v)  *min_element(v.begin(),v.end())     // find min element in vector
inline bool isPrime(int v) {if(v==1) return false; if(v <= 3)return true;if ( v % 2 == 0 || v % 3 == 0)return false;int i = 5;while (i * i <= v) {if (v % i == 0 || v % (i + 2) == 0)return false;i += 6;}return true;}
inline void printbin(int v,int upto=10) {cout<<v<<"-> ";for (int i = upto; i >= 0; --i) {cout<<checkbit(v,i) sped}cout ed}
bool isEqual(double a, double b, double epsilon = 1e-9) {return abs(a - b) <= epsilon * (1ll + max(abs(a), abs(b)));}
bool isLessEqual(double a,double b, double epsilon = 1e-9) {return isEqual(a,b,epsilon) || a<b;}
inline bool limit_check(long long a, long long b, int max_bits = 59) {if (a == 0 || b == 0) return true;return msb(a) + msb(b) >= 128 - max_bits;}

// Free to use :}






void solve() {
  // Global Variables
  int n, m, k, q;
  string str;
  //------------------------------RISHU------------------------------//

  int len;
  ci n>>len;

  vp a(n);
  for (auto&[x,y]:a)ci x>>y;

  double reach=0,r=0;
  auto [xo,yo]=a[0];

  fl(1,n) {
    const auto &[xn,yn]=a[i];
    double niche=2.0*(xn-xo);
    double upr=((xn-xo)*(xn-xo))+(yo*yo)-(yn*yn);
    double cal=(upr/niche)*(upr/niche);
    double newR=sqrt(yn*yn+(cal));
    reach=xo+sqrt(newR*newR-yo*yo);
    r=max(r,newR);

    double left=xn-sqrt(r*r-yn*yn);
    double right=xn+sqrt(r*r-yn*yn);
    assert(isLessEqual(left,reach));

    reach=max(reach,right);
  }
  if (reach<len) {
    double newR=(len-xo)*(len-xo)+(yo*yo);
    double right=xo+sqrt(r*r-yo*yo);

    assert(isLessEqual(len,right));
    r=max(r,newR);
  }


  cout<<fixed<<setprecision(4)<<r<<endl;
}

signed main() {
  Code By NeverSpot
  const auto begin = chrono::high_resolution_clock::now();


  solve();
  const auto end = chrono::high_resolution_clock::now();
  const auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end - begin);
  cerr <<fixed<<setprecision(10)<<"Time measured: " << static_cast<double>(elapsed.count()) * 1e-9 << " seconds.\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...