// {{{ y0105w49 template 21N30 // hi mom #ifndef NULL // #include #include #endif #include 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 &_gbd35(ostream &os,const T &x) { return _gbd3(os,x); // why?? } 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) _gbd35(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) begin(v),end(v) #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 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 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<>; const int e0=1, e1=10, e2=100, e3=1000; const int e4=10*e3, e5=100*e3, e6=1000*e3; const int e7=10*e6, e8=100*e6, e9=1000*e6; const long long e12=1LL*e3*e9, e15=1LL*e6*e9, e18=1LL*e9*e9; using ulll=__uint128_t; using lll=__int128_t; using ull=unsigned long long; using ll=long long; unsigned long long START_TIME=chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count(); inline unsigned long long now_U_03BC_s() { return chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; } const char *fmt_time(unsigned 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=JO&&getenv("sd")?atoi(getenv("sd")):unsigned(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("finished (early) in",fmt_time()); 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 arg1=stoi(args[1]); } inp=!arg1; if(JO && getenv("EMACS")) EMACS=1; dbgt(arg1,seed,args); MAIN(); dbgt("gg;wp"); } using flt=double; //CARE const flt U_03B5_=(flt)1e-8; const flt U_03C4_=(flt)(2*acosl(-1)); const int inf=e9+99; const ll linf=1LL*e9*e9+99; // }}} const int P=e9+7;//998'244'353; #define flt fltflt using fltflt=double; ll sq(int x) { return 1LL*x*x; } struct circ { int x,y,r; vector> arcs; void read() { inr(x,-e6,e6), inr(y,-e6,e6), inr(r,e6); } string pretty() const { return fmt("C",x,y,r,arcs); } friend ostream &operator<<(ostream &os,const circ &c) { return os< isect(const circ &o) const { ll dd=D2(o); ll num=sq(r)+D2(o)-sq(o.r); flt den=2*r*sqrt(dd); flt U_03C6_=acos(num/den); dbg(U_03C6_); flt U_03B8_=atan2(o.y-y,o.x-x); flt U_03B8_l=U_03B8_-U_03C6_; if(U_03B8_l<-U_03C4_/2) U_03B8_l+=U_03C4_; flt U_03B8_r=U_03B8_+U_03C6_; if(U_03B8_r>+U_03C4_/2) U_03B8_r-=U_03C4_; return {U_03B8_l,U_03B8_r}; } flt f(int O,flt U_03B8_l,flt U_03B8_r) const { flt sl=sin(U_03B8_l),cl=cos(U_03B8_l); flt sr=sin(U_03B8_r),cr=cos(U_03B8_r); flt Z=1LL*(y-O)*(cr-cl); Z+=.5*r*(cr*sr-cl*sl); Z-=.5*r*(U_03B8_r-U_03B8_l); dbg(x,y,r,U_03B8_l,U_03B8_r,Z); return Z*r; } flt Q(int L,int R,int D,int U) const { if(L>=x+r) return 0; if(R<=x-r) return 0; if(D>=y+r) return 0; if(U<=y-r) return 0; int h=0; vector> evts; if(L>x-r) { flt U_03B8_=acos(flt(L-x)/r); ++h; evts.pb({-U_03B8_,1}); evts.pb({U_03B8_,0}); } if(Ry-r) { flt U_03B8_=asin(flt(D-y)/r); if(U_03B8_>0) ++h, evts.pb({U_03C4_/2-U_03B8_,0}); else evts.pb({-U_03C4_/2-U_03B8_,0}); evts.pb({U_03B8_,1}); } if(U=r) break; x=evts[ii].fi; evts[ii++].se?--h:++h; } } dbg(L,R,D,U,x,y,r,Z); return Z; } }; vector> delis(flt L,flt R,vector> todel) { vector> evts={{L,1},{R,0}}; for(auto [l,r]:todel) { l=max(l,L); r=min(r,R); if(l>=r) continue; evts.pb({l,0}); evts.pb({r,1}); } sort(all(evts)); int h=1; flt pr=L; vector> Z; for(auto [x,b]:evts) { if(!h && x>L) Z.pb({pr,x}); assert(h>=0); b?--h:++h; pr=x; } assert(h==1 && pr==R); return Z; } void _main() { /* CURSOR START */ int n,q; ine(n,arg1), ine(q,arg1); vector cs(n); for(circ &c:cs) c.read(); for(int i=0;i> todel; for(const circ &cc:cs) if(c.real_isect(cc)) { auto [U_03B8_l,U_03B8_r]=c.isect(cc); assert(U_03B8_l!=U_03B8_r); if(U_03B8_l> todel; for(const circ &c:cs) { if(abs(c.y-y)>=c.r) continue; ll dd=sq(c.r)-sq(c.y-y); flt dx=sqrt(dd); todel.pb({c.x-dx,c.x+dx}); } auto ivals=delis(l,r,todel); for(auto [xl,xr]:ivals) Z+=(xr-xl)*(y-d); Z-=1LL*w*(y-d); } dbg(l,d,w,h,Z); for(const circ &c:cs) Z+=c.Q(l,r,d,u); cout<