// {{{ y0105w49 template 22M14 // hi mom #ifndef NULL #ifdef __GNUC__ #ifndef __clang__ // #include #include #include #define EXTS #else #ifdef ARST #include #else #ifndef _GLIBCXX_NO_ASSERT #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include // #include #include #include #include // #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif #if __cplusplus >= 201402L #include #endif #if __cplusplus >= 201703L #include #include // #include #include #include // #include #include #include #endif #if __cplusplus >= 202002L #include #include #include #include #if __cpp_impl_coroutine # include #endif #include #include #include #include // #include #include // #include // #include #include #endif #if __cplusplus > 202002L // #include // #include #if __has_include() # include #endif #include #endif #endif #endif #else #error "unsupported" #endif #endif using namespace std; #ifdef ARST #define JO 1 #define OJ 0 #else #define JO 0 #define OJ 1 #endif #define STR(x) #x #define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true) #define Wsave GCCDIAG(push) #define Wpop GCCDIAG(pop) #define Wsupp(w) GCCDIAG(ignored "-W" w) #define Wpush(w) Wsave; Wsupp(w) #define typeof __typeof__ namespace gbd_ns { template struct is_iterable { template static long check(...); template static char check(int,typename T::const_iterator = C().end()); enum { value = sizeof(check(0)) == sizeof(char), neg_value = sizeof(check(0)) != sizeof(char) }; }; template struct _gbd3C; template ostream &_gbd3(ostream &os,const T &x) { return _gbd3C::call(os,x); } template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'< ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'< ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); } template ostream &_gbd4(ostream &os,const pair &p) { _gbd3(os<<'(',p.first); _gbd3(os<<',',p.second); return os<<')'; } template struct _gbd4_tupleC { static void call(ostream &os,const T &t) { _gbd4_tupleC::call(os,t); os<<','<(t); } }; template struct _gbd4_tupleC { static void call(ostream &os,const T &t) { os<(t); } }; template ostream &_gbd4(ostream &os,const tuple &t) { os<<'('; _gbd4_tupleC,sizeof...(Types)>::call(os,t); return os<<')'; } template<> ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; } template ostream &_gbd4(ostream &os,const T &x) { return os< struct _gbd3C { template static ostream &call(ostream &os,enable_if_t::value,const T> &V) { os<<"{"; bool ff=0; for(const auto &E:V) _gbd3_5(ff?os<<",":os,E), ff=1; return os<<"}"; } template static ostream &call(ostream &os,enable_if_t::neg_value,const T> &x) { return _gbd4(os,x); } }; template ostream &_gbd2(ostream &os,bool,vector::iterator nm,const T &x,Args&&... args); ostream &_gbd2(ostream &os,bool,vector::iterator) { return os; } template ostream &_gbd2(ostream &os,bool fi,vector::iterator nm,const char *x,Args&&... args) { return _gbd2(os<<(fi?"":" ")< ostream &_gbd2(ostream &os,bool fi,vector::iterator nm,const T &x,Args&&... args) { return _gbd2(_gbd3(os<<(fi?"":" ")<<*nm<<"=",x),0,nm+1,args...); } vector split(string s) { vector Z; string z=""; s+=','; int dep=0; for(char c:s) { if(c==',' && !dep) Z.push_back(z),z=""; else z+=c; if(c=='(' || c=='{' || c=='[') ++dep; if(c==')' || c=='}' || c==']') --dep; } return Z; } template ostream &_gbd1(ostream &os,const string &nm,Args&&... args) { return _gbd2(os,1,split(nm).begin(),args...); } template string _gbd1(const string &nm,Args&&... args) { ostringstream oss; _gbd2(oss,1,split(nm).begin(),args...); return oss.str(); } } bool DBG=1,EMACS=0; #define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"< struct _y_combinator_result { Fun _fun; template explicit _y_combinator_result(T &&fun) : _fun(forward(fun)) {} template decltype(auto) operator()(Args &&... args) { return _fun(ref(*this),forward(args)...); } }; template [[nodiscard]] decltype(auto) fix(Fun &&fun) { return _y_combinator_result>(forward(fun)); } #define nop void() #define sz(x) (int((x).size())) #define all(v) (v).begin(),(v).end() #define sortu(v) (sort(all(v)), (v).resize(unique(all(v))-begin(v))) #define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else #define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else #define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k) #define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k) #define get(x,i) get(x) template bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; } #define fi first #define se second #define pb push_back #define eb emplace_back #ifdef EXTS template using omap=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template using oset=omap; template using rope=__gnu_cxx::rope; using dbitset=tr2::dynamic_bitset<>; #endif constexpr int e0=1, e1=10, e2=100, e3=1000; constexpr int e4=10*e3, e5=100*e3, e6=1000*e3; constexpr int e7=10*e6, e8=100*e6, e9=1000*e6; constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9; constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12; constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15; constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18; constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27; using ulll=__uint128_t; using lll=__int128_t; using ull=unsigned long long; using ll=long long; using ld=long double; long long START_TIME=chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count(); inline long long now_U_03BC_s() { return chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; } const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; } #define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0) int arg1; bool inp; vector args; unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5); mt19937 igen(seed<<1),gen(seed<<1|1); #define irand(...) _rand(igen,__VA_ARGS__) #define rand(...) _rand(gen,__VA_ARGS__) template enable_if_t::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution(l,r)(g); } template enable_if_t::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); } [[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits::max()); } template enable_if_t::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution(l,r)(g); } bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); } template T _rand(mt19937 &g,initializer_list il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); } template T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; } template T _rand(mt19937 &g,initializer_list il,initializer_list wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution(wt)(g)); } #define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle") #define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop)) #define inr(x,...) ine(x,irand(__VA_ARGS__)) #define endl '\n' string garb; void exit0() { DBG=1; dbgt("gg (early)"); exit(0); } #ifndef MAIN #define MAIN _main #endif void MAIN(); int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit); arg1=0,args={argv,argv+argc}; if(sz(args)>1) { if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin); else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin); else arg1=stoi(args[1]); } inp=!arg1; if(JO && getenv("EMACS")) EMACS=1; dbgt(arg1,seed,args); #ifdef QUIET DBG=0; #endif MAIN(); DBG=1; dbgt("gg;wp"); return 0; } constexpr int inf=e9+99; constexpr ll linf=1LL*e9*e9+99; #if __cplusplus >= 202002L constexpr long double U_03C4__ld=2*numbers::pi_v; #else const long double U_03C4__ld=2*acosl(-1); #endif #define U_03C4_ ((flt)U_03C4__ld) constexpr long double U_03B5__ld=1e-8l; #define U_03B5_ ((flt)U_03B5__ld) // }}} using flt=ld; //CARE constexpr int P=e9+7;//998'244'353; #define midpoint(x,y) ((x+y)>>1) using pt=complex; ll xx(pt x,pt y) { return imag(x*conj(y)); } bool LEF(pt x,pt y,pt z) { return xx(y-x,z-y)<0; } bool RIG(pt x,pt y,pt z) { return xx(y-x,z-y)>0; } const int N=100<<10; pt z[N],lef[N],rig[N]; void f(int l,int r) { if(l==r) return; int ml=midpoint(l,r); int mr=ml+1; assert(l<=ml && ml> pts; for(int i=l;i<=r;i++) pts.pb({z[i],i}); sort(all(pts),[&](auto x,auto y) { return imag(x.fi) lefs={{-inf,0}},rigs={{inf,0}}; for(auto [p,i]:pts) { auto &qh=i<=ml?rigs:lefs; int L=0,R=sz(qh)-1; for(;L=mr && imag(p)==imag(ah.back()) && real(p)>=real(ah.back())) continue; for(;sz(ah)>=2;) { if(i<=ml && imag(p)==imag(ah.back()) && real(p)>real(ah.back())) { ah.pop_back(); continue; } if(i>=mr && imag(p)==imag(ah.back()) && real(p)1) assert(l>real(lef[i-1])); // static set> ss; // assert(ss.insert({x,y}).se); z[i]={x,y}; lef[i]={l,0}; rig[i]={r,0}; } f(1,n); flt Z=0; for(int i=1;i<=n;i++) { // dbg(i,z[i],lef[i],rig[i]); if(LEF(lef[i],z[i],rig[i])) return cout<<-1<real(rig[i])) dd=rig[i]; else assert(0); dd-=z[i]; complex DD={(flt)real(dd),(flt)imag(dd)}; Z+=abs(DD)*imag(z[i])/imag(-dd); } cout<