想定解と違う…。
https://yukicoder.me/problems/no/1074
問題
2次元座標において、原点を含むような、軸に平行な長方形がN個与えられる。
これらの領域の和集合を順次取るとき、面積の差分を求めよ。
解法
各象限についてみていく。
mapを使い凸包と面積を管理していくと、O(NlogN)で処理できる。
このテクは下記でも使用している。
Codeforces #419 Div1 D. Karen and Cards - kmjp's blog
JOI2011-2012 Day1 Fish 解説
class AreaRect { map<ll,ll> M; public: ll sum; AreaRect() { M[0]=1LL<<60; M[1LL<<60]=0; sum=0; } void add(ll x,ll y) { auto k=M.lower_bound(x); if(k->second>=y) return; while(prev(M.lower_bound(x))->second<=y) { auto p=*prev(M.lower_bound(x)); M.erase(p.first); sum-=(p.first-prev(M.lower_bound(p.first))->first)*(p.second-M.lower_bound(p.first)->second); } sum += (x-prev(M.lower_bound(x))->first)*(y-M.lower_bound(x)->second); M[x]=y; } }; AreaRect M[4]; int N; int X1,X2,Y1,Y2; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll pre=0; FOR(i,N) { cin>>X1>>Y1>>X2>>Y2; M[0].add(-X1,-Y1); M[1].add(-X1,Y2); M[2].add(X2,-Y1); M[3].add(X2,Y2); ll sum=M[0].sum+M[1].sum+M[2].sum+M[3].sum; cout<<sum-pre<<endl; pre=sum; } }
まとめ
ライブラリ化しているので瞬殺でした。