// NOI2017 分身术 - onion layers + t-separated arc enumeration + O(log) lower-bridge merge.
// Compile with -DTEST to self-test against brute on stdin (gen.py format).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 100005;
static const int MAXK = 130;
static const int PEEL = 105; // recursion depth <= k <= 100, so peel 105 convex layers max
static ll X[MAXN], Y[MAXN];
static inline ll crs3(int a,int b,int c){ return (X[b]-X[a])*(Y[c]-Y[b])-(Y[b]-Y[a])*(X[c]-X[b]); }
static inline ll cross2(int a,int b){ return X[a]*Y[b]-Y[a]*X[b]; }
static inline ll crsP(int o,int a,int b){ return (X[a]-X[o])*(Y[b]-Y[o])-(Y[a]-Y[o])*(X[b]-X[o]); }
static int K;
static vector<int> vert[MAXK];
static int h[MAXK];
static vector<ll> pref[MAXK];
static int layer_of[MAXN], pos_of[MAXN];
static int loLen[MAXK];
static vector<int> upV[MAXK]; // x-increasing upper chain of each layer
static vector<ll> upPref[MAXK]; // prefix cross-sums along upV
static int upLen[MAXK];
static vector<int> delLo[MAXK], delUp[MAXK]; // per-query sorted deleted indices in loV(=vert[0..loLen-1]) / upV
static bool xSafe = false; // true iff every chain is strictly x-increasing (no vertical edges)
static vector<pair<int,int>> dels;
static vector<int> delByLayer[MAXK];
static int delMark[MAXN];
static int gOrder[MAXN];
static int gPts[MAXN];
static int gInner[MAXN]; static int gInnerCnt=0;
static int delStamp = 0;
static int n, m;
static inline ll tval(int A,int B,int p){ return (X[p]-X[A])*(X[B]-X[A]) + (Y[p]-Y[A])*(Y[B]-Y[A]); }
static inline ll hval(int A,int B,int p){ return crs3(A,B,p); }
// find argmin/argmax of a linear function (crs3 or tval w.r.t. A,B) over layer d's
// two x-monotone chains, via binary search on the unimodal value sequence.
static void extrema(int d, int A, int B, bool useCrs, int& mn, int& mx){
int hd = h[d], LL = loLen[d];
const int* V = vert[d].data();
auto gv = [&](int t){
int p = V[t];
return useCrs ? crs3(A,B,p) : tval(A,B,p);
};
auto maxOn = [&](int lo,int hi){ int l=lo, r=hi; while(l<r){ int mid=(l+r)>>1; if(gv(mid) < gv(mid+1)) l=mid+1; else r=mid; } int e=(gv(lo)>=gv(hi))?lo:hi; if(gv(l)>gv(e)) e=l; return e; };
auto minOn = [&](int lo,int hi){ int l=lo, r=hi; while(l<r){ int mid=(l+r)>>1; if(gv(mid) > gv(mid+1)) l=mid+1; else r=mid; } int e=(gv(lo)<=gv(hi))?lo:hi; if(gv(l)<gv(e)) e=l; return e; };
int M = maxOn(0, LL-1);
if(LL < hd){ int M2 = maxOn(LL, hd-1); if(gv(M2) > gv(M)) M = M2; }
int m = minOn(0, LL-1);
if(LL < hd){ int m2 = minOn(LL, hd-1); if(gv(m2) < gv(m)) m = m2; }
mn = m; mx = M;
}
// tangent from external point P to layer d (strictly-convex CCW polygon).
// right tangent: cross(P, vert[t], vert[w]) >= 0 for all w != t.
// left tangent : cross(P, vert[t], vert[w]) <= 0 for all w != t.
// Local characterization (exactly one vertex in the non-collinear case): both neighbors lie on the same side.
static int tangentRight(int P, int d){
int hd = h[d];
for(int t=0;t<hd;t++){
int pr=(t-1+hd)%hd, nx=(t+1)%hd;
if(crsP(P, vert[d][t], vert[d][pr]) >= 0 && crsP(P, vert[d][t], vert[d][nx]) >= 0)
return t;
}
return -1;
}
static int tangentLeft(int P, int d){
int hd = h[d];
for(int t=0;t<hd;t++){
int pr=(t-1+hd)%hd, nx=(t+1)%hd;
if(crsP(P, vert[d][t], vert[d][pr]) <= 0 && crsP(P, vert[d][t], vert[d][nx]) <= 0)
return t;
}
return -1;
}
// lower-hull arc of layer d (h>=3) w.r.t. chord A,B, returned t-increasing: (s,len,step).
// step=+1: chain[k]=vert[d][(s+k)%h]; step=-1: vert[d][(s-k+h)%h].
// Returns false if empty; fallback set on collinear ambiguity.
static bool lowerHullArc(int d, int A, int B, int& s, int& len, int& step, bool& fallback, bool& allBelow){
int hd = h[d];
auto g = [&](int t){ return hval(A,B,vert[d][t % hd]); };
int m, M; extrema(d, A, B, true, m, M);
ll gM = g(M), gm = g(m);
allBelow = false;
if(gm > 0) return false; // all above AB
if(gM < 0){ // all below: exposed arc is delimited by the point-to-chain
// tangents from the two anchors A and B (not the t-extremes).
allBelow = true;
// If this layer has deletions, the caller will use the exact materialize path
// (the deletions can expose the next layer's "top" vertices), so skip the tangent scan.
if(!delByLayer[d].empty()){ fallback = true; return false; }
int TA = tangentRight(A, d);
int TB = tangentLeft(B, d);
if(TA < 0 || TB < 0){ fallback = true; return false; }
int lenCCW = (TB - TA + hd) % hd + 1;
if(lenCCW == 1){ s = TA; len = 1; step = +1; return true; }
{
ll tTA = tval(A,B,vert[d][TA]);
ll tTB = tval(A,B,vert[d][TB]);
ll tB = tval(A,B,B);
if(tTA < 0 || tTA > tB || tTB < 0 || tTB > tB){ fallback = true; return false; }
int p0 = vert[d][TA];
int p1 = vert[d][(TA + 1) % hd];
int pLm1 = vert[d][(TB - 1 + hd) % hd];
int pL = vert[d][TB];
ll d0 = tval(A,B,p1) - tval(A,B,p0);
ll dL = tval(A,B,pL) - tval(A,B,pLm1);
if((d0 > 0 && dL < 0) || (d0 < 0 && dL > 0) || d0 == 0 || dL == 0){
fallback = true; return false;
}
if(d0 > 0){ s = TA; step = +1; len = lenCCW; }
else { s = TB; step = -1; len = lenCCW; }
}
return true;
}
// intersecting
if(gM == 0 || gm == 0){ fallback = true; return false; }
int start=M, end=m; if(end<start) end+=hd;
int lo=start, hi=end;
while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
int fa = lo % hd;
start=m; end=M; if(end<start) end+=hd;
lo=start; hi=end;
while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
int fb = (lo-1+hd) % hd;
// The below-AB arc [fa..fb] must be t-monotone for the bridge merge.
// t is bitonic along the convex arc, so compare the t-slopes at the two ends:
// opposite signs => interior t-extreme => non-monotone => fallback.
if(fa != fb){
int na = (fa + 1) % hd;
int pb = (fb - 1 + hd) % hd;
ll d0 = tval(A,B,vert[d][na]) - tval(A,B,vert[d][fa]);
ll dL = tval(A,B,vert[d][fb]) - tval(A,B,vert[d][pb]);
if((d0 > 0 && dL < 0) || (d0 < 0 && dL > 0) || d0 == 0 || dL == 0){
fallback = true; return false;
}
}
int a = fa, b = fb; if(b < a) b += hd;
ll ta = tval(A,B,vert[d][a%hd]), tb = tval(A,B,vert[d][b%hd]);
if(ta <= tb){ s = fa; step = +1; len = b-a+1; }
else { s = fb; step = -1; len = b-a+1; }
return true;
}
// ---- implicit chains ----
struct Piece { int d, s, step, kStart, kLen; };
struct Chain {
vector<Piece> pc;
vector<int> szPref;
vector<ll> csPref; // csPref[i] = cross-sum of pieces[0..i-1] + bridge edges among them
int size() const { return szPref.empty() ? 0 : szPref.back(); }
ll total() const { return csPref.empty() ? 0 : csPref.back(); }
};
static inline int piecePoint(const Piece& p, int k){
int hd = h[p.d];
int idx = p.s + (p.kStart + k) * p.step;
idx %= hd; if(idx < 0) idx += hd;
return vert[p.d][idx];
}
static inline int pieceFirst(const Piece& p){ return piecePoint(p, 0); }
static inline int pieceLast(const Piece& p){ return piecePoint(p, p.kLen - 1); }
static ll pieceCS(const Piece& p){
int hd = h[p.d];
int len = p.kLen;
if(len <= 1) return 0;
if(p.step == +1){
int b = p.s + p.kStart;
return pref[p.d][b + len - 1] - pref[p.d][b];
} else {
int Rh = p.s - p.kStart + hd;
int Lh = p.s - p.kStart - len + 1 + hd;
return pref[p.d][Lh] - pref[p.d][Rh];
}
}
static int chainPoint(const Chain& c, int k){
int idx = (int)(upper_bound(c.szPref.begin(), c.szPref.end(), k) - c.szPref.begin()) - 1;
return piecePoint(c.pc[idx], k - c.szPref[idx]);
}
static void rebuildChainCS(Chain& c){
int np = (int)c.pc.size();
c.csPref.assign(np+1, 0);
for(int i=0;i<np;i++){
ll v = 0;
if(i > 0) v += cross2(pieceLast(c.pc[i-1]), pieceFirst(c.pc[i]));
v += pieceCS(c.pc[i]);
c.csPref[i+1] = c.csPref[i] + v;
}
}
static ll chainPrefixCS(const Chain& c, int cnt){ // cross-sum of first cnt points (cnt-1 edges)
if(cnt <= 1) return 0;
int idx = (int)(upper_bound(c.szPref.begin(), c.szPref.end(), cnt-1) - c.szPref.begin()) - 1;
ll s = c.csPref[idx];
if(idx > 0) s += cross2(pieceLast(c.pc[idx-1]), pieceFirst(c.pc[idx]));
const Piece& p = c.pc[idx];
Piece q = p; q.kLen = (cnt-1) - c.szPref[idx] + 1;
s += pieceCS(q);
return s;
}
static ll chainSuffixCS(const Chain& c, int start){ // cross-sum of points start..end
int sz = c.size();
if(start >= sz-1) return 0;
return c.total() - chainPrefixCS(c, start+1);
}
static void chainFromPoint(int p, Chain& c){
c.pc.clear(); c.szPref.clear(); c.csPref.clear();
c.pc.push_back({layer_of[p], pos_of[p], +1, 0, 1});
c.szPref.push_back(0); c.szPref.push_back(1);
rebuildChainCS(c);
}
static void chainFromArc(int d, int s, int len, int step, Chain& c){
c.pc.clear(); c.szPref.clear(); c.csPref.clear();
if(len <= 0){ rebuildChainCS(c); return; }
c.pc.push_back({d, s, step, 0, len});
c.szPref.push_back(0); c.szPref.push_back(len);
rebuildChainCS(c);
}
static int lowerTangentJ(int oi, const Chain& B){
int q = B.size();
int lo=0, hi=q-1;
while(lo<hi){
int mid=(lo+hi)>>1;
if(crsP(oi, chainPoint(B,mid), chainPoint(B,mid+1)) < 0) lo=mid+1; else hi=mid;
}
return lo;
}
static pair<int,int> lowerBridge(const Chain& A, const Chain& B){
int p = A.size();
if(p == 1) return {0, lowerTangentJ(chainPoint(A,0), B)};
int lo=0, hi=p-1, ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int j = lowerTangentJ(chainPoint(A,mid), B);
bool ok = (mid==0) || (crs3(chainPoint(A,mid-1), chainPoint(A,mid), chainPoint(B,j)) > 0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
int i=ans, j=lowerTangentJ(chainPoint(A,i), B);
return {i,j};
}
static void mergeInPlace(Chain& cur, const Chain& C, int i, int j){
int idxA = (int)(upper_bound(cur.szPref.begin(), cur.szPref.end(), i) - cur.szPref.begin()) - 1;
cur.pc.resize(idxA+1);
cur.pc[idxA].kLen = i - cur.szPref[idxA] + 1;
int idxB = (int)(upper_bound(C.szPref.begin(), C.szPref.end(), j) - C.szPref.begin()) - 1;
{
Piece q = C.pc[idxB];
q.kStart += (j - C.szPref[idxB]);
q.kLen -= (j - C.szPref[idxB]);
if(q.kLen > 0) cur.pc.push_back(q);
}
for(int t=idxB+1;t<(int)C.pc.size();t++) cur.pc.push_back(C.pc[t]);
cur.szPref.clear(); cur.szPref.push_back(0);
for(auto& p : cur.pc) cur.szPref.push_back(cur.szPref.back() + p.kLen);
rebuildChainCS(cur);
}
static inline int arcPoint(int d, int s, int step, int k){
int hd = h[d];
int idx = s + k*step; idx %= hd; if(idx<0) idx += hd;
return vert[d][idx];
}
// enumerate surviving arcs of layers d.. for chord A,B, clipped to t in [tL,tR], t-increasing.
static void collectArcs(int d, int A, int B, ll tL, ll tR, vector<Piece>& out, bool& fallback){
if(d >= K) return;
int hd = h[d];
if(hd < 3){
// degenerate layer: at most 2 points. add below-AB points (in [tL,tR]) as single points.
int tmp[4];
int cnt = 0;
for(int t=0;t<hd;t++){
int p = vert[d][t];
if(delMark[p] == delStamp) continue;
if(hval(A,B,p) < 0){
ll tv = tval(A,B,p);
if(tv >= tL && tv <= tR) tmp[cnt++] = p;
}
}
if(cnt == 2){
ll t0 = tval(A,B,tmp[0]), t1 = tval(A,B,tmp[1]);
if(t0 > t1) swap(tmp[0], tmp[1]);
}
for(int i=0;i<cnt;i++){
out.push_back({layer_of[tmp[i]], pos_of[tmp[i]], +1, 0, 1});
}
return;
}
int s, len, step;
bool allBelow = false;
if(!lowerHullArc(d, A, B, s, len, step, fallback, allBelow)) return;
if(allBelow){
// layer entirely below AB: deletions on it can expose "top" vertices -> fallback.
if(!delByLayer[d].empty()){ fallback = true; return; }
}
// clip to [tL,tR] (t increasing in k)
int klo = len, khi = -1;
{
int l=0, r=len-1;
while(l<=r){ int mid=(l+r)>>1; if(tval(A,B,arcPoint(d,s,step,mid)) >= tL){ klo=mid; r=mid-1; } else l=mid+1; }
l=0; r=len-1;
while(l<=r){ int mid=(l+r)>>1; if(tval(A,B,arcPoint(d,s,step,mid)) <= tR){ khi=mid; l=mid+1; } else r=mid-1; }
}
if(klo > khi) return;
int sllen = khi - klo + 1;
// deleted offsets within sub-arc [klo,khi]
vector<int> dp;
for(int p : delByLayer[d]){
int k;
if(step==+1) k = (p - s + hd) % hd;
else k = (s - p + hd) % hd;
if(k >= klo && k <= khi) dp.push_back(k - klo);
}
if(dp.size()>1){ sort(dp.begin(), dp.end()); dp.erase(unique(dp.begin(), dp.end()), dp.end()); }
int cur = 0, i = 0;
while(i < (int)dp.size()){
int pk = dp[i], qk = pk;
while(i+1 < (int)dp.size() && dp[i+1] == qk+1) qk = dp[++i];
// surviving piece [cur, pk-1]
if(pk-1 >= cur){
int ss = arcPoint(d, s, step, klo + cur);
// find ss's layer pos and store as a t-increasing piece starting at ss
out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, pk - cur});
}
// recurse for gap [pk, qk]
ll tL2 = (pk > 0) ? tval(A,B,arcPoint(d,s,step,klo+pk-1)) : tL;
ll tR2 = (qk+1 < sllen) ? tval(A,B,arcPoint(d,s,step,klo+qk+1)) : tR;
collectArcs(d+1, A, B, tL2, tR2, out, fallback);
cur = qk + 1;
i++;
}
if(cur <= sllen-1){
out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, sllen - cur});
}
}
// fallback: single-pass materialize + sort + graham. Collects every surviving point
// strictly below the chord AB across all inner layers in ONE pass (O(total below-arc size)),
// instead of recursing once per deleted gap (which re-materializes each deeper layer's
// below-arc and becomes exponential for all-below layers with deletions spread across them).
static vector<int> E;
static int findArcSlow(int A, int B, int d2, int& fa, int& fb){
int h2 = h[d2];
int e0=-1; bool anyNon=false;
for(int t=0;t<h2;t++){ if(crs3(A,B,vert[d2][t])<0){ if(e0<0)e0=t; } else anyNon=true; }
if(e0==-1) return 0;
if(!anyNon){ fa=0; fb=h2-1; return 1; }
fa=e0; fb=e0;
for(int st=0; st<h2 && crs3(A,B,vert[d2][(fb+1)%h2])<0; st++) fb=(fb+1)%h2;
for(int st=0; st<h2 && crs3(A,B,vert[d2][(fa-1+h2)%h2])<0; st++) fa=(fa-1+h2)%h2;
return 1;
}
static int findArcFast(int A, int B, int d2, int& fa, int& fb){
int h2=h[d2];
if(h2<3) return -1;
int LL=loLen[d2];
auto g=[&](int t){ return crs3(A,B,vert[d2][t%h2]); };
int m,M; extrema(d2, A, B, true, m, M);
ll gM=g(M), gm=g(m);
if(gM<0){ fa=0; fb=h2-1; return 1; }
if(gm>0) return 0;
if(gM==0||gm==0) return -1;
int start=M,end=m; if(end<start) end+=h2;
int lo=start,hi=end; while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
fa=lo%h2;
start=m; end=M; if(end<start) end+=h2;
lo=start;hi=end; while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
fb=(lo-1+h2)%h2;
return 1;
}
static void buildExposed(int d, int A, int B){
for(int d2=d+1; d2<K; d2++){
int h2 = h[d2];
if(h2 < 3){
for(int t=0;t<h2;t++){
int p = vert[d2][t];
if(delMark[p] == delStamp) continue;
if(hval(A,B,p) < 0) E.push_back(p);
}
continue;
}
int fa,fb;
int r = findArcFast(A,B,d2,fa,fb);
if(r == 0) continue;
if(r == -1){ r = findArcSlow(A,B,d2,fa,fb); if(r == 0) continue; }
int lo = fa, hi = (fb >= fa) ? fb : fb + h2;
for(int t=lo; t<=hi; t++){
int p = vert[d2][t % h2];
if(delMark[p] != delStamp) E.push_back(p);
}
}
}
static ll convexChain(int A, vector<int>& E, int B){
if(E.empty()) return cross2(A,B);
static vector<int> pts; pts.clear();
pts=E; pts.push_back(A); pts.push_back(B);
sort(pts.begin(), pts.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
pts.erase(unique(pts.begin(),pts.end()),pts.end());
if(pts.size()<3) return cross2(A,B);
static int stk[MAXN*2]; int top=0;
for(int idx:pts){ while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
int lower=top;
for(int t=(int)pts.size()-2;t>=0;t--){ int idx=pts[t]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
top--;
int iA=-1,iB=-1;
for(int i=0;i<top;i++){ if(stk[i]==A)iA=i; if(stk[i]==B)iB=i; }
ll s=0;
if(stk[(iA+1)%top]==B){
for(int k=iA;;k=(k-1+top)%top){ int nxt=(k-1+top)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
} else {
for(int k=iA;;k=(k+1)%top){ int nxt=(k+1)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
}
return s;
}
static bool anyCollinearExtreme(int A, int B){
for(int d=1; d<K; d++){
int hd = h[d];
if(hd < 3) continue;
int tmn, tmx; extrema(d, A, B, false, tmn, tmx);
int pr=(tmn-1+hd)%hd, nx=(tmn+1)%hd;
if(tval(A,B,vert[d][pr])==tval(A,B,vert[d][tmn])) return true;
if(tval(A,B,vert[d][nx])==tval(A,B,vert[d][tmn])) return true;
pr=(tmx-1+hd)%hd; nx=(tmx+1)%hd;
if(tval(A,B,vert[d][pr])==tval(A,B,vert[d][tmx])) return true;
if(tval(A,B,vert[d][nx])==tval(A,B,vert[d][tmx])) return true;
}
return false;
}
// true if the outermost inner layer (first with h>=3) is entirely below chord A->B.
static bool innerAllBelow(int A, int B){
int d0 = 1;
while(d0 < K && h[d0] < 3) d0++;
if(d0 >= K) return false;
int m, M; extrema(d0, A, B, true, m, M);
return crs3(A,B,vert[d0][M]) < 0;
}
// O(log h) tangent from external point P to convex polygon layer d, kind=+1 right / -1 left.
static int ucArr[MAXN+5];
static int tangentPoly(int P, int d, int kind){
int hd = h[d], LL = loLen[d];
int cand[10]; int nc=0;
auto add=[&](int idx){ for(int i=0;i<nc;i++) if(cand[i]==idx) return; cand[nc++]=idx; };
auto crsLo=[&](int i, int j){ return crsP(P, vert[d][i], vert[d][j]); };
if(LL >= 2){
{int lo=0,hi=LL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsLo(mid,mid+1)<0) lo=mid+1; else hi=mid; } add(lo);}
{int lo=0,hi=LL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsLo(mid,mid+1)>0) lo=mid+1; else hi=mid; } add(lo);}
}
int uL=0; ucArr[uL++]=0;
for(int i=hd-1;i>=LL;i--) ucArr[uL++]=i;
if(uL>1 && ucArr[uL-1]!=LL-1) ucArr[uL++]=LL-1;
if(uL>=2){
auto crsUp=[&](int i, int j){ return crsP(P, vert[d][ucArr[i]], vert[d][ucArr[j]]); };
{int lo=0,hi=uL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsUp(mid,mid+1)<0) lo=mid+1; else hi=mid; } add(ucArr[lo]);}
{int lo=0,hi=uL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsUp(mid,mid+1)>0) lo=mid+1; else hi=mid; } add(ucArr[lo]);}
}
add(0); add(LL-1);
int best=-1; ll bestDist=-1;
auto consider=[&](int t){
int pr=(t-1+hd)%hd, nx=(t+1)%hd;
ll a=crsP(P, vert[d][t], vert[d][pr]);
ll b=crsP(P, vert[d][t], vert[d][nx]);
bool ok = (kind==+1) ? (a>=0 && b>=0) : (a<=0 && b<=0);
if(!ok) return;
ll dd=(X[vert[d][t]]-X[P])*(X[vert[d][t]]-X[P])+(Y[vert[d][t]]-Y[P])*(Y[vert[d][t]]-Y[P]);
if(dd>bestDist){ bestDist=dd; best=t; }
};
for(int i=0;i<nc;i++) consider(cand[i]);
if(best>=0) return best;
for(int t=0;t<hd;t++) consider(t);
return best;
}
static ll arcCS(int d, int a, int b){
if(a==b) return 0;
if(a<b) return pref[d][b]-pref[d][a];
return pref[d][h[d]]-pref[d][a]+pref[d][b];
}
// argmin (wantMin=true) / argmax (wantMin=false) of the polar angle around C over the CCW
// arc [a..b] (unwrapped, b>=a). The polar angle is unimodal on a below-AB arc (a convex
// chain whose supporting chord AB passes through the two anchors), so binary search works.
// This is the robust O(log h) replacement for tangentPoly: it never degrades when C is
// nearly on the layer's boundary (the circle-onion case), because the arc is restricted to
// the strictly-below side of the chord.
static int angleExtreme(int C, int d, int a, int b, bool wantMin){
int hd = h[d];
int l=a, r=b;
auto gt = [&](int i, int j){ return crsP(C, vert[d][i % hd], vert[d][j % hd]) < 0; }; // angle(i) > angle(j)
if(wantMin){
while(l<r){ int mid=(l+r)>>1; if(gt(mid, mid+1)) l=mid+1; else r=mid; }
} else {
while(l<r){ int mid=(l+r)>>1; if(!gt(mid, mid+1)) l=mid+1; else r=mid; }
}
return l % hd;
}
// Point-to-convex-polygon tangents (argmin/argmax polar angle around C over the FULL layer).
// The polar angle around an external C is cyclic bitonic (one peak, one valley). The peak/valley
// are the point-to-layer tangents; each is either an angle extremum on one of the two x-monotone
// chains (found by the unimodal cross-product search below) or one of the two extreme vertices
// (leftmost/rightmost). We gather those O(1) candidates, verify with the O(1) local predicate,
// and only fall back to the correct wrap-safe O(h) scan for degenerate/collinear cases.
static int tangentMono(int P, int d, int ckind, int lo, int hi, bool wantMax); // fwd (defined below)
// Global cache for the point-to-polygon tangent (a pure function of (anchor C, layer d) once the
// layer is fixed). Test 16 reuses a tiny set of anchors (the obtuse-triangle vertices), so this
// turns the per-gap tangent into an O(1) hit after the first few computations.
static const int TCACHE_SZ = 1<<17;
static ll tcacheKey[TCACHE_SZ];
static int tcacheVal[TCACHE_SZ];
static inline int tcacheGet(ll key){
int s = (int)(key & (TCACHE_SZ-1));
for(int t=0;t<TCACHE_SZ;t++){
int i=(s+t)&(TCACHE_SZ-1);
if(tcacheKey[i]==key) return tcacheVal[i];
if(tcacheKey[i]==0) return -1; // empty (key is never 0 since d>=0 and C>=0 but C can be 0 -> key=d could be 0; use sentinel)
}
return -1;
}
static inline void tcachePut(ll key, int val){
int s = (int)(key & (TCACHE_SZ-1));
for(int t=0;t<TCACHE_SZ;t++){
int i=(s+t)&(TCACHE_SZ-1);
if(tcacheKey[i]==key || tcacheKey[i]==0){ tcacheKey[i]=key; tcacheVal[i]=val; return; }
}
}
static int cyclicMin(int C, int d){ return 0; /*PROBE*/
ll key = ((ll)C << 9) | (ll)(d << 1) | 0LL;
int cached = tcacheGet(key);
if(cached >= 0) return cached;
int hd=h[d];
int STEP = max(1, (int)sqrt((double)hd));
auto g=[&](int i){ return crs3(vert[d][i], vert[d][(i+1)%hd], C); };
ll prev = g(0);
int res = 0;
for(int i = STEP; i < hd + STEP; i += STEP){
int idx = i % hd;
ll cur = g(idx);
if(prev < 0 && cur >= 0){
int lo = (i - STEP + hd) % hd;
for(int k = 0; k < STEP; k++){
int t = (lo + k) % hd;
int pr = (t - 1 + hd) % hd;
if(g(pr) < 0 && g(t) >= 0){ res=t; goto done; }
}
}
prev = cur;
}
for(int t=0;t<hd;t++){ int pr=(t-1+hd)%hd; if(g(pr) < 0 && g(t) >= 0){ res=t; goto done; } }
done:
tcachePut(key, res);
return res;
}
static int cyclicMax(int C, int d){ return 0; /*PROBE*/
ll key = ((ll)C << 9) | (ll)(d << 1) | 1LL;
int cached = tcacheGet(key);
if(cached >= 0) return cached;
int hd=h[d];
int STEP = max(1, (int)sqrt((double)hd));
auto g=[&](int i){ return crs3(vert[d][i], vert[d][(i+1)%hd], C); };
ll prev = g(0);
int res = 0;
for(int i = STEP; i < hd + STEP; i += STEP){
int idx = i % hd;
ll cur = g(idx);
if(prev >= 0 && cur < 0){
int lo = (i - STEP + hd) % hd;
for(int k = 0; k < STEP; k++){
int t = (lo + k) % hd;
int pr = (t - 1 + hd) % hd;
if(g(pr) >= 0 && g(t) < 0){ res=t; goto done; }
}
}
prev = cur;
}
for(int t=0;t<hd;t++){ int pr=(t-1+hd)%hd; if(g(pr) >= 0 && g(t) < 0){ res=t; goto done; } }
done:
tcachePut(key, res);
return res;
}
// argmax / argmin of the linear function crs3(P,Q,·) over layer d (cyclic bitonic, same
// structure as the polar-angle extrema above). These replace the chain-based `extrema` in the
// hot recursion: the linear function increases to a single peak and decreases to a single
// valley around a convex polygon, so a rotated-array minimum search on the derivative sign
// finds both extrema in O(log h) with far fewer cross products.
static int linearMax(int P, int Q, int d){ // argmax of crs3(P,Q,·)
int n = h[d];
ll dx = X[Q]-X[P], dy = Y[Q]-Y[P];
const int* V = vert[d].data();
auto g = [&](int i){ return X[V[i]]*dy - Y[V[i]]*dx; };
auto dec = [&](int i){ return g(i) > g((i+1)%n); };
int lo=0, hi=n-1;
while(lo<hi){
int mid=(lo+hi)>>1;
if((dec(mid)?0:1) > (dec(hi)?0:1)) lo=mid+1; else hi=mid;
}
int peak=lo;
{
int pr=(peak-1+n)%n, nx=(peak+1)%n;
if(g(peak) >= g(pr) && g(peak) >= g(nx))
return peak;
}
int best=0;
for(int t=1;t<n;t++) if(g(t) > g(best)) best=t;
return best;
}
static int linearMin(int P, int Q, int d){ // argmin of crs3(P,Q,·)
int n = h[d];
ll dx = X[Q]-X[P], dy = Y[Q]-Y[P];
const int* V = vert[d].data();
auto g = [&](int i){ return X[V[i]]*dy - Y[V[i]]*dx; };
auto asc = [&](int i){ return g(i) <= g((i+1)%n); };
int lo=0, hi=n-1;
while(lo<hi){
int mid=(lo+hi)>>1;
if((asc(mid)?0:1) > (asc(hi)?0:1)) lo=mid+1; else hi=mid;
}
int valley=lo;
{
int pr=(valley-1+n)%n, nx=(valley+1)%n;
if(g(valley) <= g(pr) && g(valley) <= g(nx))
return valley;
}
int best=0;
for(int t=1;t<n;t++) if(g(t) < g(best)) best=t;
return best;
}
// per-query memo for exposedAreaTangent: its result is a pure function of (d,P,Q) given the
// fixed per-query deletion set, so cache by packed (d,P,Q). Epoch-coded by delStamp (incremented
// per query) so no clearing is needed: a slot with gen != delStamp is empty.
static const int MEMO_SZ = 1<<13;
static struct { ll key; ll area; int gen; } memo[MEMO_SZ];
static inline ll memoKey(int d, int P, int Q){ return ((ll)d << 40) | ((ll)P << 20) | (ll)Q; }
static ll* memoFind(ll key){
int s = (int)(key & (MEMO_SZ-1));
for(int t=0;t<MEMO_SZ;t++){
int i=(s+t)&(MEMO_SZ-1);
if(memo[i].gen == delStamp){ if(memo[i].key == key) return &memo[i].area; }
else return nullptr;
}
return nullptr;
}
static void memoInsert(ll key, ll area){
int s = (int)(key & (MEMO_SZ-1));
for(int t=0;t<MEMO_SZ;t++){
int i=(s+t)&(MEMO_SZ-1);
if(memo[i].gen != delStamp){ memo[i].gen=delStamp; memo[i].key=key; memo[i].area=area; return; }
if(memo[i].key == key){ memo[i].area=area; return; }
}
}
static ll exposedAreaTangentRaw(int d, int P, int Q, bool& fb);
static ll exposedAreaTangent(int d, int P, int Q, bool& fb){
ll key = memoKey(d, P, Q);
ll* hit = memoFind(key);
if(hit){ fb = false; return *hit; }
ll r = exposedAreaTangentRaw(d, P, Q, fb);
if(!fb) memoInsert(key, r);
return r;
}
// tangent-delimited exposed-chain area from P to Q through surviving allBelow layers d..K-1.
static ll exposedAreaTangentRaw(int d, int P, int Q, bool& fb){
if(d >= K) return cross2(P, Q);
int hd = h[d];
if(hd < 3){
// Degenerate innermost layer (<=2 surviving leftover points). The exposed chain
// is the convex hull of {P,Q} + the surviving points below chord P->Q; compute it
// exactly (at most 4 points) instead of naively concatenating (which wrongly keeps
// a below point that lies inside the triangle P-Q-other).
int arr[4]; int ac=0;
arr[ac++]=P; arr[ac++]=Q;
for(int t=0;t<hd;t++){ int p=vert[d][t]; if(delMark[p]!=delStamp && crs3(P,Q,p) < 0) arr[ac++]=p; }
if(ac==2) return exposedAreaTangent(d+1, P, Q, fb);
if(ac==3) return cross2(P,arr[2])+cross2(arr[2],Q);
// ac==4: convex hull of {P,Q,a,b}
for(int i=0;i<ac;i++) for(int j=i+1;j<ac;j++)
if(X[arr[j]]<X[arr[i]] || (X[arr[j]]==X[arr[i]] && Y[arr[j]]<Y[arr[i]])) swap(arr[i],arr[j]);
int stk[8]; int top=0;
for(int i=0;i<ac;i++){ int idx=arr[i]; while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
int lower=top;
for(int i=ac-2;i>=0;i--){ int idx=arr[i]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
top--;
int iP=-1,iQ=-1;
for(int i=0;i<top;i++){ if(stk[i]==P)iP=i; if(stk[i]==Q)iQ=i; }
if(iP<0||iQ<0) return cross2(P,Q);
ll s=0;
if(stk[(iP+1)%top]==Q){ for(int k=iP;;k=(k-1+top)%top){ int nxt=(k-1+top)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==Q) break; } }
else { for(int k=iP;;k=(k+1)%top){ int nxt=(k+1)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==Q) break; } }
return s;
}
int M = linearMax(P, Q, d);
ll gM = crs3(P,Q,vert[d][M]);
int m = 0; ll gm = 0;
if(gM > 0){
m = linearMin(P, Q, d);
gm = crs3(P,Q,vert[d][m]);
if(gm >= 0) return cross2(P, Q); // all above chord (or tangent) -> deeper layers also above
}
// gm < 0: some point strictly below. Determine the below arc [fa..fb].
bool allBelow = (gM <= 0); // gM==0 = tangent touch, still handled by the full-layer tangents
int fa, fbEnd;
if(allBelow){ fa = 0; fbEnd = hd - 1; }
else {
int lo=M, hi=m; if(hi<lo) hi+=hd;
while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(P,Q,vert[d][mid%hd])>=0) lo=mid+1; else hi=mid; }
fa = lo % hd;
lo=m; hi=M; if(hi<lo) hi+=hd;
while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(P,Q,vert[d][mid%hd])<0) lo=mid+1; else hi=mid; }
fbEnd = (lo-1+hd) % hd;
}
int TA, TB;
if(allBelow){
// whole layer below (or tangent): exposed arc delimited by the point-to-layer tangents,
// found via the cyclic polar-angle extrema (robust even when P/Q nearly touch the layer).
TA = cyclicMin(P, d);
TB = cyclicMax(Q, d);
} else {
// intersecting: tangents live inside the below arc; find them by the unimodal polar
// angle (robust when P/Q are nearly on the layer boundary, as in circle-onion data).
int a=fa, b=fbEnd; if(b<a) b+=hd;
TA = angleExtreme(P, d, a, b, true);
TB = angleExtreme(Q, d, a, b, false);
}
int len = (TB - TA + hd) % hd + 1;
int dpos[130]; int dc=0;
for(int p : delByLayer[d]){
int off=(p-TA+hd)%hd;
if(off<len) dpos[dc++]=off;
}
if(dc>1){ sort(dpos, dpos+dc); dc = (int)(unique(dpos, dpos+dc) - dpos); }
// Deleted tangent vertex -> materialize (rare, but the correct tangent to the surviving
// arc is not simply the adjacent vertex).
if(dc>0 && (dpos[0]==0 || dpos[dc-1]==len-1)){ fb=true; return 0; }
ll area=0;
{
int firstSurv=TA;
if(dc>0 && dpos[0]==0) firstSurv=(TA-1+hd)%hd;
area += cross2(P, vert[d][firstSurv]);
}
int cur=0; int i=0;
while(i<dc){
int pk=dpos[i], qk=pk;
while(i+1<dc && dpos[i+1]==qk+1) qk=dpos[++i];
if(pk-1>=cur){ int a=(TA+cur)%hd, b=(TA+pk-1)%hd; area+=arcCS(d,a,b); }
int Pa=(TA+pk-1)%hd; if(Pa<0)Pa+=hd;
int Qa=(TA+qk+1)%hd;
area += exposedAreaTangent(d+1, vert[d][Pa], vert[d][Qa], fb);
if(fb) return 0;
cur=qk+1; i++;
}
if(cur<=len-1){ int a=(TA+cur)%hd; area+=arcCS(d,a,TB); }
{
int lastSurv=TB;
if(dc>0 && dpos[dc-1]==len-1) lastSurv=(TB+1)%hd;
area += cross2(vert[d][lastSurv], Q);
}
return area;
}
// sort-free materialize: collect A,B and surviving f<0 inner points in pre-sorted (x,y)
// order, then Andrew monotone chain. Returns the same value as buildExposed+convexChain.
static ll convexChainSorted(int A, int B){
bool ab = innerAllBelow(A,B);
// if allBelow and no inner deletions, the hull is just {A,B} + outermost inner layer
// (deeper layers are strictly inside and never on the hull).
int cnt = 0;
if(ab){
bool anyInnerDel = false;
for(int dd=1; dd<K; dd++) if(!delByLayer[dd].empty()){ anyInnerDel = true; break; }
if(!anyInnerDel){
gPts[cnt++] = A; gPts[cnt++] = B;
int d0 = 1; while(d0 < K && h[d0] < 3) d0++;
if(d0 < K){
for(int t=0;t<h[d0];t++){
int p = vert[d0][t];
if(delMark[p] == delStamp) continue;
gPts[cnt++] = p;
}
}
sort(gPts, gPts+cnt, [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
goto hull;
}
}
for(int ii=0; ii<n; ii++){
int p = gOrder[ii];
if(p == A || p == B){ gPts[cnt++] = p; continue; }
if(layer_of[p] < 1) continue;
if(delMark[p] == delStamp) continue;
if(!ab && crs3(A,B,p) >= 0) continue;
gPts[cnt++] = p;
}
hull:
if(cnt < 3) return cross2(A,B);
static int stk[MAXN*2]; int top=0;
for(int t=0;t<cnt;t++){ int idx=gPts[t]; while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
int lower=top;
for(int t=cnt-2;t>=0;t--){ int idx=gPts[t]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
top--;
int iA=-1,iB=-1;
for(int i=0;i<top;i++){ if(stk[i]==A)iA=i; if(stk[i]==B)iB=i; }
ll s=0;
if(stk[(iA+1)%top]==B){
for(int k=iA;;k=(k-1+top)%top){ int nxt=(k-1+top)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
} else {
for(int k=iA;;k=(k+1)%top){ int nxt=(k+1)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
}
return s;
}
// ===================== X-monotone fast path =====================
// For a gap (A,B) on L0, the exposed chain is the surviving points strictly below the
// chord A->B (hval<0), which for each inner layer is a contiguous CCW arc (raw below-arc
// for the intersecting case, tangent-delimited for the allBelow case). That arc is walked
// x-INCREASING (a convex x-monotone chain for the general-position judge data) and clipped
// by X-intervals along the ORIGINAL chord, so the recursion visits O(k) nodes per query.
// A.x<B.x -> lower envelope (lowerBridge), A.x>B.x -> upper envelope (upperBridge, negated).
// upper common tangent of two x-increasing UPPER chains (sign-flipped lowerBridge).
static int upperTangentJ(int oi, const Chain& B){
int q = B.size();
int lo=0, hi=q-1;
while(lo<hi){
int mid=(lo+hi)>>1;
if(crsP(oi, chainPoint(B,mid), chainPoint(B,mid+1)) > 0) lo=mid+1; else hi=mid;
}
return lo;
}
static pair<int,int> upperBridge(const Chain& A, const Chain& B){
int p = A.size();
if(p == 1) return {0, upperTangentJ(chainPoint(A,0), B)};
int lo=0, hi=p-1, ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int j = upperTangentJ(chainPoint(A,mid), B);
bool ok = (mid==0) || (crs3(chainPoint(A,mid-1), chainPoint(A,mid), chainPoint(B,j)) < 0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
int i=ans, j=upperTangentJ(chainPoint(A,i), B);
return {i,j};
}
// below-AB arc of layer d (h>=3) walked x-increasing: (s,len,step) in vert[d] order.
// step=+1: chain[k]=vert[d][(s+k)%h]; step=-1: vert[d][(s-k+h)%h].
// Returns false if empty (all above AB); fallback set on collinear / non-x-monotone arc.
static bool lowerHullArcX(int d, int A, int B, int& s, int& len, int& step, bool& fallback){
int hd = h[d];
auto g = [&](int t){ return hval(A,B,vert[d][t % hd]); };
int m, M; extrema(d, A, B, true, m, M);
ll gM = g(M), gm = g(m);
if(gm > 0) return false; // all above AB
int fa, fb;
if(gM < 0){
// all below: exposed arc delimited by the point-to-layer tangents from A,B.
fa = cyclicMin(A, d);
fb = cyclicMax(B, d);
if(fa < 0 || fb < 0){ fallback = true; return false; }
} else if(gM == 0 || gm == 0){
fallback = true; return false;
} else {
// intersecting: below-arc [f0..f1] via the two sign changes of g, then the exposed
// arc is delimited by the point-to-layer tangents from A,B inside that below-arc.
int f0, f1;
int start=M, end=m; if(end<start) end+=hd;
int lo=start, hi=end;
while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
f0 = lo % hd;
start=m; end=M; if(end<start) end+=hd;
lo=start; hi=end;
while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
f1 = (lo-1+hd) % hd;
int a=f0, b=f1; if(b<a) b+=hd;
fa = angleExtreme(A, d, a, b, true);
fb = angleExtreme(B, d, a, b, false);
}
// A deleted tangent vertex shifts the tangent to the surviving arc (not simply the
// adjacent vertex); that rare case is left to the (correct) tangent/materialize path.
if(delMark[vert[d][fa]] == delStamp || delMark[vert[d][fb]] == delStamp){ fallback = true; return false; }
int lenCCW = (fb - fa + hd) % hd + 1;
// x-monotonicity: the arc must not contain the layer's leftmost(0)/rightmost(loLen-1)
// as an interior point (otherwise x is bimodal along the CCW arc).
if(lenCCW > 1){
int a = fa, b = fa + lenCCW - 1;
auto interior = [&](int p){ return (a < p && p < b) || (a < p+hd && p+hd < b); };
if(interior(0) || interior(loLen[d]-1)){ fallback = true; return false; }
}
// walk x-increasing
if(X[vert[d][fa]] <= X[vert[d][fb]]){ s = fa; step = +1; }
else { s = fb; step = -1; }
len = lenCCW;
return true;
}
// enumerate surviving below-AB arcs of layers d.. for chord A,B, clipped to x in [xL,xR],
// x-increasing. Recurse on the ORIGINAL chord with x-intervals (non-exponential).
static void collectArcsX(int d, int A, int B, ll xL, ll xR, vector<Piece>& out, bool& fallback){
if(d >= K) return;
int hd = h[d];
if(hd < 3){
int tmp[4]; int cnt = 0;
for(int t=0;t<hd;t++){
int p = vert[d][t];
if(delMark[p] == delStamp) continue;
if(hval(A,B,p) < 0){
ll xv = X[p];
if(xv >= xL && xv <= xR) tmp[cnt++] = p;
}
}
if(cnt == 2 && X[tmp[0]] > X[tmp[1]]) swap(tmp[0], tmp[1]);
for(int i=0;i<cnt;i++){
out.push_back({layer_of[tmp[i]], pos_of[tmp[i]], +1, 0, 1});
}
return;
}
int s, len, step;
if(!lowerHullArcX(d, A, B, s, len, step, fallback)) return;
// clip to [xL,xR] (x increasing in k)
int klo = len, khi = -1;
{
int l=0, r=len-1;
while(l<=r){ int mid=(l+r)>>1; if(X[arcPoint(d,s,step,mid)] >= xL){ klo=mid; r=mid-1; } else l=mid+1; }
l=0; r=len-1;
while(l<=r){ int mid=(l+r)>>1; if(X[arcPoint(d,s,step,mid)] <= xR){ khi=mid; l=mid+1; } else r=mid-1; }
}
if(klo > khi) return;
int sllen = khi - klo + 1;
vector<int> dp;
for(int p : delByLayer[d]){
int k;
if(step==+1) k = (p - s + hd) % hd;
else k = (s - p + hd) % hd;
if(k >= klo && k <= khi) dp.push_back(k - klo);
}
if(dp.size()>1){ sort(dp.begin(), dp.end()); dp.erase(unique(dp.begin(), dp.end()), dp.end()); }
int cur = 0, i = 0;
while(i < (int)dp.size()){
int pk = dp[i], qk = pk;
while(i+1 < (int)dp.size() && dp[i+1] == qk+1) qk = dp[++i];
if(pk-1 >= cur){
out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, pk - cur});
}
ll xL2 = (pk > 0) ? X[arcPoint(d,s,step,klo+pk-1)] : xL;
ll xR2 = (qk+1 < sllen) ? X[arcPoint(d,s,step,klo+qk+1)] : xR;
collectArcsX(d+1, A, B, xL2, xR2, out, fallback);
cur = qk + 1;
i++;
}
if(cur <= sllen-1){
out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, sllen - cur});
}
}
// exposed-chain area for a gap (A,B) via x-monotone arcs. Assumes A.x != B.x.
static bool xExposedArea(int A, int B, ll& res){
static vector<Piece> arcs;
arcs.clear();
bool fallback = false;
if(X[A] < X[B]){
collectArcsX(1, A, B, X[A], X[B], arcs, fallback);
if(fallback) return false;
static Chain cur, C, Bc;
chainFromPoint(A, cur);
for(auto& p : arcs){
chainFromArc(p.d, p.s, p.kLen, p.step, C);
auto pr = lowerBridge(cur, C);
mergeInPlace(cur, C, pr.first, pr.second);
}
chainFromPoint(B, Bc);
auto pr = lowerBridge(cur, Bc);
mergeInPlace(cur, Bc, pr.first, pr.second);
res = cur.total();
return true;
} else {
collectArcsX(1, A, B, X[B], X[A], arcs, fallback);
if(fallback) return false;
static Chain cur, C, Bc;
chainFromPoint(B, cur);
for(auto& p : arcs){
chainFromArc(p.d, p.s, p.kLen, p.step, C);
auto pr = upperBridge(cur, C);
mergeInPlace(cur, C, pr.first, pr.second);
}
chainFromPoint(A, Bc);
auto pr = upperBridge(cur, Bc);
mergeInPlace(cur, Bc, pr.first, pr.second);
res = -(cur.total());
return true;
}
}
// ===================== straddle: x-bimodal below-arc via two x-monotone halves =====================
// A straddle gap has the exposed chain x-bimodal: it goes from the left anchor, increases to an
// x-extreme of the below-region, then decreases to the right anchor (or vice-versa). The below-arc
// of each layer is tangent-delimited (cyclicMin/cyclicMax for allBelow, angleExtreme for
// intersecting), and is split at the layer's leftmost/rightmost into a lower-chain piece (x inc)
// and an upper-chain piece (x inc). Each piece's area is a prefix-sum; pieces across consecutive
// layers are merged with the lower/upper bridge (never materializing points). Non-exponential: the
// recursion descends only into deleted gaps, clipped by disjoint x-intervals.
struct SPiece { int d; int kind; int s; int len; }; // kind 0=vert[d] (lower, x inc), 1=upV[d] (x inc)
struct SChain {
vector<SPiece> pc;
vector<int> szPref;
vector<ll> csPref;
int size() const { return szPref.empty() ? 0 : szPref.back(); }
ll total() const { return csPref.empty() ? 0 : csPref.back(); }
};
static inline int sPoint(const SPiece& p, int k){ return (p.kind==0) ? vert[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int sFirst(const SPiece& p){ return sPoint(p,0); }
static inline int sLast(const SPiece& p){ return sPoint(p,p.len-1); }
static ll sCS(const SPiece& p){
if(p.len<=1) return 0;
if(p.kind==0) return pref[p.d][p.s+p.len-1] - pref[p.d][p.s];
return upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s];
}
static int sChainPoint(const SChain& c, int k){
int idx=(int)(upper_bound(c.szPref.begin(),c.szPref.end(),k)-c.szPref.begin())-1;
return sPoint(c.pc[idx], k-c.szPref[idx]);
}
static void sRebuild(SChain& c){
int np=(int)c.pc.size();
c.csPref.assign(np+1,0);
for(int i=0;i<np;i++){
ll v=0;
if(i>0) v+=cross2(sLast(c.pc[i-1]), sFirst(c.pc[i]));
v+=sCS(c.pc[i]);
c.csPref[i+1]=c.csPref[i]+v;
}
}
static void sFromPoint(int p, SChain& c){
c.pc.clear(); c.szPref.clear(); c.csPref.clear();
c.pc.push_back({layer_of[p], 0, pos_of[p], 1});
c.szPref.push_back(0); c.szPref.push_back(1);
sRebuild(c);
}
static void sFromPiece(const SPiece& p, SChain& c){
c.pc.clear(); c.szPref.clear(); c.csPref.clear();
if(p.len<=0){ sRebuild(c); return; }
c.pc.push_back(p);
c.szPref.push_back(0); c.szPref.push_back(p.len);
sRebuild(c);
}
static int sLowerTangentJ(int oi, const SChain& B){
int q=B.size(); int lo=0,hi=q-1;
while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,sChainPoint(B,mid),sChainPoint(B,mid+1))<0) lo=mid+1; else hi=mid; }
return lo;
}
// O(log |A|) reversed tangent from point P (right of A) to SChain A: two-level binary search.
static int sRevTangentLower(const SChain& A, int P){
int m=(int)A.pc.size(), sz=A.size();
if(sz==1) return 0;
int t=-1;
if(m>=2){
int lo=0,hi=m-2;
while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sLast(A.pc[mid]), sFirst(A.pc[mid+1]), P)<0){ t=mid; hi=mid-1; } else lo=mid+1; }
}
if(t>=0){
const SPiece& q=A.pc[t]; int L=q.len; int r=-1;
if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)<0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r>=0) return A.szPref[t]+r;
return A.szPref[t]+L-1;
} else {
const SPiece& q=A.pc[m-1]; int L=q.len; int r=-1;
if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)<0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r>=0) return A.szPref[m-1]+r;
return sz-1;
}
}
static int sRevTangentUpper(const SChain& A, int P){
int m=(int)A.pc.size(), sz=A.size();
if(sz==1) return 0;
int t=-1;
if(m>=2){
int lo=0,hi=m-2;
while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sLast(A.pc[mid]), sFirst(A.pc[mid+1]), P)>0){ t=mid; hi=mid-1; } else lo=mid+1; }
}
if(t>=0){
const SPiece& q=A.pc[t]; int L=q.len; int r=-1;
if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)>0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r>=0) return A.szPref[t]+r;
return A.szPref[t]+L-1;
} else {
const SPiece& q=A.pc[m-1]; int L=q.len; int r=-1;
if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)>0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r>=0) return A.szPref[m-1]+r;
return sz-1;
}
}
static pair<int,int> sLowerBridge(const SChain& A, const SChain& B){
int p=A.size();
if(p==1) return {0, sLowerTangentJ(sChainPoint(A,0),B)};
if(B.size()==1) return {sRevTangentLower(A, sChainPoint(B,0)), 0};
int ci=0, cj=0;
for(int it=0; it<64; it++){
int jn=sLowerTangentJ(sChainPoint(A,ci),B);
int in=sRevTangentLower(A, sChainPoint(B,jn));
if(in==ci && jn==cj) return {in,jn};
ci=in; cj=jn;
}
int lo=0,hi=p-1,ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int j=sLowerTangentJ(sChainPoint(A,mid),B);
bool ok=(mid==0)||(crs3(sChainPoint(A,mid-1),sChainPoint(A,mid),sChainPoint(B,j))>0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
int i=ans, j=sLowerTangentJ(sChainPoint(A,i),B);
return {i,j};
}
static int sUpperTangentJ(int oi, const SChain& B){
int q=B.size(); int lo=0,hi=q-1;
while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,sChainPoint(B,mid),sChainPoint(B,mid+1))>0) lo=mid+1; else hi=mid; }
return lo;
}
static pair<int,int> sUpperBridge(const SChain& A, const SChain& B){
int p=A.size();
if(p==1) return {0, sUpperTangentJ(sChainPoint(A,0),B)};
if(B.size()==1) return {sRevTangentUpper(A, sChainPoint(B,0)), 0};
int ci=0, cj=0;
for(int it=0; it<64; it++){
int jn=sUpperTangentJ(sChainPoint(A,ci),B);
int in=sRevTangentUpper(A, sChainPoint(B,jn));
if(in==ci && jn==cj) return {in,jn};
ci=in; cj=jn;
}
int lo=0,hi=p-1,ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int j=sUpperTangentJ(sChainPoint(A,mid),B);
bool ok=(mid==0)||(crs3(sChainPoint(A,mid-1),sChainPoint(A,mid),sChainPoint(B,j))<0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
int i=ans, j=sUpperTangentJ(sChainPoint(A,i),B);
return {i,j};
}
static void sMerge(SChain& cur, const SChain& C, int i, int j){
int idxA=(int)(upper_bound(cur.szPref.begin(),cur.szPref.end(),i)-cur.szPref.begin())-1;
cur.pc.resize(idxA+1);
cur.pc[idxA].len = i - cur.szPref[idxA] + 1;
int idxB=(int)(upper_bound(C.szPref.begin(),C.szPref.end(),j)-C.szPref.begin())-1;
{ SPiece q=C.pc[idxB]; q.s+=(j-C.szPref[idxB]); q.len-=(j-C.szPref[idxB]); if(q.len>0) cur.pc.push_back(q); }
for(int t=idxB+1;t<(int)C.pc.size();t++) cur.pc.push_back(C.pc[t]);
cur.szPref.clear(); cur.szPref.push_back(0);
for(auto& p:cur.pc) cur.szPref.push_back(cur.szPref.back()+p.len);
sRebuild(cur);
}
// upV index of a vert position p (upper-chain point or the two extremes).
static inline int upIdxOfD(int d, int p){ return (p==0) ? 0 : h[d]-p; }
// Tangent-delimited below-arc of layer d w.r.t. chord A->B. Returns TA,TB (vert indices) and the
// wrap flags (strictly interior leftmost/rightmost). Mirrors exposedAreaTangentRaw's arc logic.
static bool belowArcTangents(int d, int A, int B, int& TA, int& TB, bool& wrapR, bool& wrapL){
int hd=h[d];
int M=linearMax(A,B,d);
ll gM=crs3(A,B,vert[d][M]);
int m=0; ll gm=0;
if(gM>0){
m=linearMin(A,B,d);
gm=crs3(A,B,vert[d][m]);
if(gm>=0) return false; // all above chord
}
bool allBelow=(gM<=0);
if(allBelow){
TA=cyclicMin(A,d);
TB=cyclicMax(B,d);
} else {
int lo=M, hi=m; if(hi<lo) hi+=hd;
while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(A,B,vert[d][mid%hd])>=0) lo=mid+1; else hi=mid; }
int fa=lo%hd;
lo=m; hi=M; if(hi<lo) hi+=hd;
while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(A,B,vert[d][mid%hd])<0) lo=mid+1; else hi=mid; }
int fbEnd=(lo-1+hd)%hd;
int a=fa, b=fbEnd; if(b<a) b+=hd;
TA=angleExtreme(A,d,a,b,true);
TB=angleExtreme(B,d,a,b,false);
}
int lenCCW=(TB-TA+hd)%hd+1;
int a=TA, b=a+lenCCW-1;
wrapR=(a<loLen[d]-1)&&(b>loLen[d]-1);
wrapL=(a>0)&&(b>hd);
return true;
}
// lower-chain portion of the below-arc (vert[d] arc, x increasing). Empty => the arc lives on the
// upper chain (only possible when x-monotone).
static bool loPieceRange(int d, int TA, int TB, bool wrapR, bool wrapL, int& s, int& len){
int LL=loLen[d];
if(wrapR){ s=TA; len=LL-TA; return len>0; }
if(wrapL){ s=0; len=TB+1; return len>0; }
if(TA<=TB && TB<=LL-1){ s=TA; len=TB-TA+1; return true; }
return false;
}
static bool upPieceRange(int d, int TA, int TB, bool wrapR, bool wrapL, int& s, int& len){
int hd=h[d], uL=upLen[d];
if(wrapR){ s=upIdxOfD(d,TB); len=uL-s; return len>0; }
if(wrapL){ s=0; len=upIdxOfD(d,TA)+1; return len>0; }
if(TA>=loLen[d] && TB>=loLen[d] && TA<=TB){ int a=upIdxOfD(d,TA), b=upIdxOfD(d,TB); s=b; len=a-b+1; return len>0; }
return false;
}
// emit pieces of layer d's below-arc for the lower (kind=0) or upper (kind=1) hull, x-clipped to
// [xL,xR], recursing into deleted gaps. Each below-arc is split into a lower-chain piece and an
// upper-chain piece; the ALIGNED piece contributes its full sub-chains (with interior deletion
// recursion), the NON-ALIGNED piece contributes only its first/last surviving points (its x-extremes,
// which matter when the shared leftmost/rightmost is deleted). fallback=true only for the rare
// x-monotone-on-the-other-chain case.
static int sdpos[130];
static bool gXmono = false; // true: x-monotone single-chain mode (no fallback on the other chain)
static int gD0 = -1, gTA0 = -1, gTB0 = -1; // precomputed tangents of the outermost inner layer
// unimodal polar-angle tangent from external point P to an x-monotone chain (ckind 0=vert lower,
// 1=upV upper), indices [lo..hi] x-increasing. wantMax = argmax angle (left tangent), else argmin.
static int tangentMono(int P, int d, int ckind, int lo, int hi, bool wantMax){
int l=lo, r=hi;
while(l<r){
int mid=(l+r)>>1;
int a=(ckind==0)?vert[d][mid]:upV[d][mid];
int b=(ckind==0)?vert[d][mid+1]:upV[d][mid+1];
ll c=crsP(P,a,b); // >0: angle(b) > angle(a)
if(wantMax){ if(c>0) l=mid+1; else r=mid; }
else { if(c<0) l=mid+1; else r=mid; }
}
return l;
}
static void emitChainPieces(int d, int kind, int A, int B, ll xL, ll xR, vector<SPiece>& out, bool& fallback){
if(d<0 || d>=K) return;
int hd=h[d];
if(hd<3){
int tmp[4]; int cnt=0;
for(int t=0;t<hd;t++){
int p=vert[d][t];
if(delMark[p]==delStamp) continue;
if(hval(A,B,p)<0){ ll xv=X[p]; if(xv>=xL && xv<=xR) tmp[cnt++]=p; }
}
if(cnt==2 && X[tmp[0]]>X[tmp[1]]) swap(tmp[0],tmp[1]);
for(int t=0;t<cnt;t++) out.push_back({layer_of[tmp[t]],0,pos_of[tmp[t]],1});
return;
}
int TA,TB; bool wrapR,wrapL;
if(gXmono && d==gD0){
TA=gTA0; TB=gTB0;
int lenCCW = (TB - TA + hd) % hd + 1;
int a=TA, b=a+lenCCW-1;
wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
wrapL = (a > 0) && (b > hd);
} else if(gXmono){
// Fast x-monotone allBelow: skip the gM check and use the unimodal binary search on the
// single x-monotone chain (no wrap issues, cheaper than the cyclic tangent search).
if(kind==0){
TA = tangentMono(A,d,0,0,loLen[d]-1,false);
TB = tangentMono(B,d,0,0,loLen[d]-1,true);
} else {
int ja = tangentMono(A,d,1,0,upLen[d]-1,false);
int jb = tangentMono(B,d,1,0,upLen[d]-1,true);
TA = (ja==0) ? 0 : hd-ja;
TB = (jb==0) ? 0 : hd-jb;
}
int lenCCW = (TB - TA + hd) % hd + 1;
int a=TA, b=a+lenCCW-1;
wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
wrapL = (a > 0) && (b > hd);
} else {
if(!belowArcTangents(d,A,B,TA,TB,wrapR,wrapL)) return;
}
if(delMark[vert[d][TA]]==delStamp || delMark[vert[d][TB]]==delStamp){ fallback=true; return; }
// The below-arc's shared extreme (leftmost/rightmost) is the below-region's x-extreme; when it
// is deleted the extreme shifts to the OTHER chain (non-aligned case) -> fall back (correct, rare).
if(wrapR && delMark[vert[d][loLen[d]-1]]==delStamp){ fallback=true; return; }
if(wrapL && delMark[vert[d][0]]==delStamp){ fallback=true; return; }
int s,len;
if(kind==0){ if(!loPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
else { if(!upPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
int i=len, j=-1;
{
int lo=0, hi=len-1;
while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]>=xL){ i=mid; hi=mid-1; } else lo=mid+1; }
lo=0; hi=len-1;
while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]<=xR){ j=mid; lo=mid+1; } else hi=mid-1; }
}
if(i>j) return;
const vector<int>& dl=(kind==0)?delByLayer[d]:delUp[d];
int dc=0;
{
int lo=0, hi=(int)dl.size()-1, fst=(int)dl.size();
while(lo<=hi){ int mid=(lo+hi)>>1; if(dl[mid]>=s+i){ fst=mid; hi=mid-1; } else lo=mid+1; }
for(int t=fst; t<(int)dl.size() && dl[t]<=s+j; t++) sdpos[dc++]=dl[t]-s;
}
int nextD=d+1;
int cur=0, ii=0;
while(ii<dc){
int pk=sdpos[ii], qk=pk;
while(ii+1<dc && sdpos[ii+1]==qk+1) qk=sdpos[++ii];
if(pk-1>=cur) out.push_back({d,kind,s+cur,pk-cur});
ll xL2=(pk>0)?X[(kind==0)?vert[d][s+pk-1]:upV[d][s+pk-1]]:xL;
ll xR2=(qk+1<len)?X[(kind==0)?vert[d][s+qk+1]:upV[d][s+qk+1]]:xR;
emitChainPieces(nextD,kind,A,B,xL2,xR2,out,fallback);
if(fallback) return;
cur=qk+1; ii++;
}
if(cur<=j) out.push_back({d,kind,s+cur,j-cur+1});
}
// Exposed-chain area for a gap (A,B). wR: below-region wraps right (bimodal); wL: wraps left
// (bimodal); neither: x-monotone single-chain. Each below-arc is tangent-delimited and split into
// a lower-chain piece and an upper-chain piece; prefix sums + lower/upper bridge, never materializing.
static bool straddleExposedArea(int A, int B, bool wR, bool wL, ll& res){
static vector<SPiece> out;
static SChain cur, C;
bool fallback=false;
const ll NEG=-(1LL<<60), POS=(1LL<<60);
int la = (X[A]<=X[B]) ? A : B; // left anchor (smaller x)
int ha = (X[A]<=X[B]) ? B : A; // right anchor
// ---- lower hull (x increasing) ----
out.clear();
if(wR){ sFromPoint(la, cur); sFromPoint(ha, C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
else if(wL){ cur.pc.clear(); cur.szPref.clear(); cur.csPref.clear(); }
else { sFromPoint(la, cur); } // x-monotone: left anchor at start
emitChainPieces(1, 0, A, B, NEG, POS, out, fallback);
if(fallback) return false;
for(auto& p:out){
if(cur.size()==0){ sFromPiece(p,cur); }
else { sFromPiece(p,C); auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
}
if(wL){
if(cur.size()==0){ sFromPoint(la,cur); sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
else { sFromPoint(la,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
} else if(!wR){ // x-monotone: right anchor at end
sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
}
ll lowerSum=cur.total();
// ---- upper hull (x increasing) ----
out.clear();
if(wR){ sFromPoint(la, cur); sFromPoint(ha, C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
else if(wL){ cur.pc.clear(); cur.szPref.clear(); cur.csPref.clear(); }
else { sFromPoint(la, cur); }
emitChainPieces(1, 1, A, B, NEG, POS, out, fallback);
if(fallback) return false;
for(auto& p:out){
if(cur.size()==0){ sFromPiece(p,cur); }
else { sFromPiece(p,C); auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
}
if(wL){
if(cur.size()==0){ sFromPoint(la,cur); sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
else { sFromPoint(la,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
} else if(!wR){
sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
}
ll upperSum=cur.total();
res=lowerSum-upperSum-cross2(B,A); // signed chain A->...->B (full hull minus closing chord)
return true;
}
// ---- inline running-hull bridge/merge (NO vectors) for the x-monotone handler ----
// The accumulated x-increasing hull is kept in fixed arrays: spcArr (pieces), spcSz (prefix
// sizes), spcCs (prefix cross-sums). Each merge updates the running cross-sum in O(1) amortized
// via prefix-sum lookups (pieceCS) + the single bridge edge, instead of rebuilding the whole
// csPref vector after every merge (the O(np)-per-merge sRebuild that dominated test 16's constant).
static const int MAXSP = 1024;
static SPiece spcArr[MAXSP];
static int spcSz[MAXSP+1];
static ll spcCs[MAXSP+1];
static int spcN;
static inline int spPoint(const SPiece& p, int k){ return (p.kind==0) ? vert[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int spFirst(const SPiece& p){ return spPoint(p,0); }
static inline int spLast(const SPiece& p){ return spPoint(p,p.len-1); }
static inline ll spCS(const SPiece& p){
if(p.len<=1) return 0;
if(p.kind==0) return pref[p.d][p.s+p.len-1] - pref[p.d][p.s];
return upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s];
}
static inline int hPoint(int k){ // k-th point of the running hull (O(log np))
int lo=0, hi=spcN;
while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= k) lo=mid+1; else hi=mid; }
int idx=lo-1;
return spPoint(spcArr[idx], k - spcSz[idx]);
}
static int spLowerTangentJ(int oi, const SPiece& p){
int lo=0, hi=p.len-1;
while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) < 0) lo=mid+1; else hi=mid; }
return lo;
}
static int spUpperTangentJ(int oi, const SPiece& p){
int lo=0, hi=p.len-1;
while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) > 0) lo=mid+1; else hi=mid; }
return lo;
}
// O(log sz) reversed tangent from point P (to the RIGHT of the running hull) to the running hull:
// returns index i such that all hull points lie above (lower) / below (upper) the line hull[i]->P.
// Two-level binary search (piece level + within piece) — the "straddle" predicate is monotone along
// the weakly-convex x-increasing chain, so O(log np + log piece_len) = O(log sz) with O(1) point access.
static int spRevTangentLower(int P){
int m = spcN, sz = spcSz[spcN];
if(sz == 1) return 0;
int t = -1;
if(m >= 2){
int lo=0, hi=m-2;
while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) < 0){ t=mid; hi=mid-1; } else lo=mid+1; }
}
if(t >= 0){
const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r >= 0) return spcSz[t] + r;
return spcSz[t] + L - 1;
} else {
const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r >= 0) return spcSz[m-1] + r;
return sz - 1;
}
}
static int spRevTangentUpper(int P){
int m = spcN, sz = spcSz[spcN];
if(sz == 1) return 0;
int t = -1;
if(m >= 2){
int lo=0, hi=m-2;
while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) > 0){ t=mid; hi=mid-1; } else lo=mid+1; }
}
if(t >= 0){
const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r >= 0) return spcSz[t] + r;
return spcSz[t] + L - 1;
} else {
const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
if(r >= 0) return spcSz[m-1] + r;
return sz - 1;
}
}
// O(log |A| + log |B|) lower/upper common tangent via alternating fixpoint of the two point-to-chain
// tangents (both index functions are monotone, so it converges in <=~4 rounds in practice). Falls back
// to the O(log^2) nested search on the (never-observed) slow-convergence path.
static void spLowerBridge(const SPiece& p, int& i, int& j){
int sz = spcSz[spcN];
if(sz == 1){ i = 0; j = spLowerTangentJ(hPoint(0), p); return; }
if(p.len == 1){ i = spRevTangentLower(spPoint(p,0)); j = 0; return; }
int ci = 0, cj = 0;
for(int it=0; it<64; it++){
int jn = spLowerTangentJ(hPoint(ci), p);
int in = spRevTangentLower(spPoint(p, jn));
if(in == ci && jn == cj){ i = in; j = jn; return; }
ci = in; cj = jn;
}
int lo=0, hi=sz-1, ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int jj = spLowerTangentJ(hPoint(mid), p);
bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) > 0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
i = ans; j = spLowerTangentJ(hPoint(i), p);
}
static void spUpperBridge(const SPiece& p, int& i, int& j){
int sz = spcSz[spcN];
if(sz == 1){ i = 0; j = spUpperTangentJ(hPoint(0), p); return; }
if(p.len == 1){ i = spRevTangentUpper(spPoint(p,0)); j = 0; return; }
int ci = 0, cj = 0;
for(int it=0; it<64; it++){
int jn = spUpperTangentJ(hPoint(ci), p);
int in = spRevTangentUpper(spPoint(p, jn));
if(in == ci && jn == cj){ i = in; j = jn; return; }
ci = in; cj = jn;
}
int lo=0, hi=sz-1, ans=0;
while(lo<=hi){
int mid=(lo+hi)>>1;
int jj = spUpperTangentJ(hPoint(mid), p);
bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) < 0);
if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
}
i = ans; j = spUpperTangentJ(hPoint(i), p);
}
// truncate the running hull at global index i, then append piece p's suffix p[j..end].
// cross-sum is updated in O(1) amortized: prefix up to i stays valid, only the tail edge + piece
// suffix are added (no full recompute).
static void spAppend(const SPiece& p, int i, int j){
int idxA = 0;
{ int lo=0, hi=spcN; while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= i) lo=mid+1; else hi=mid; } idxA = lo-1; }
spcArr[idxA].len = i - spcSz[idxA] + 1;
spcN = idxA + 1;
spcSz[idxA+1] = i + 1;
spcCs[idxA+1] = spcCs[idxA] + (idxA>0 ? cross2(spLast(spcArr[idxA-1]), spFirst(spcArr[idxA])) : 0) + spCS(spcArr[idxA]);
SPiece q = p; q.s += j; q.len -= j;
if(q.len > 0){
spcArr[spcN] = q;
spcSz[spcN+1] = spcSz[spcN] + q.len;
spcCs[spcN+1] = spcCs[spcN] + cross2(spLast(spcArr[spcN-1]), spFirst(q)) + spCS(q);
spcN++;
}
}
static void mergeIntoHull(const SPiece& p, int kind){
int i, j;
if(kind==0) spLowerBridge(p, i, j); else spUpperBridge(p, i, j);
spAppend(p, i, j);
}
// emitChainPieces with inline merge into the running hull (no `out` vector materialization).
// Piece order and recursion are IDENTICAL to emitChainPieces; each piece is bridged into the
// accumulated x-monotone hull the moment it is produced (pieces arrive x-increasing).
static void emitChainPiecesMerge(int d, int kind, int A, int B, ll xL, ll xR, bool& fallback){
if(d<0 || d>=K) return;
int hd=h[d];
if(hd<3){
int tmp[4]; int cnt=0;
for(int t=0;t<hd;t++){
int p=vert[d][t];
if(delMark[p]==delStamp) continue;
if(hval(A,B,p)<0){ ll xv=X[p]; if(xv>=xL && xv<=xR) tmp[cnt++]=p; }
}
if(cnt==2 && X[tmp[0]]>X[tmp[1]]) swap(tmp[0],tmp[1]);
for(int t=0;t<cnt;t++){ SPiece pp={layer_of[tmp[t]],0,pos_of[tmp[t]],1}; mergeIntoHull(pp,kind); }
return;
}
int TA,TB; bool wrapR,wrapL;
if(gXmono && d==gD0){
TA=gTA0; TB=gTB0;
int lenCCW = (TB - TA + hd) % hd + 1;
int a=TA, b=a+lenCCW-1;
wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
wrapL = (a > 0) && (b > hd);
} else if(gXmono){
if(kind==0){
TA = tangentMono(A,d,0,0,loLen[d]-1,false);
TB = tangentMono(B,d,0,0,loLen[d]-1,true);
} else {
int ja = tangentMono(A,d,1,0,upLen[d]-1,false);
int jb = tangentMono(B,d,1,0,upLen[d]-1,true);
TA = (ja==0) ? 0 : hd-ja;
TB = (jb==0) ? 0 : hd-jb;
}
int lenCCW = (TB - TA + hd) % hd + 1;
int a=TA, b=a+lenCCW-1;
wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
wrapL = (a > 0) && (b > hd);
} else {
if(!belowArcTangents(d,A,B,TA,TB,wrapR,wrapL)) return;
}
if(delMark[vert[d][TA]]==delStamp || delMark[vert[d][TB]]==delStamp){ fallback=true; return; }
if(wrapR && delMark[vert[d][loLen[d]-1]]==delStamp){ fallback=true; return; }
if(wrapL && delMark[vert[d][0]]==delStamp){ fallback=true; return; }
int s,len;
if(kind==0){ if(!loPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
else { if(!upPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
int i=len, j=-1;
{
int lo=0, hi=len-1;
while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]>=xL){ i=mid; hi=mid-1; } else lo=mid+1; }
lo=0; hi=len-1;
while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]<=xR){ j=mid; lo=mid+1; } else hi=mid-1; }
}
if(i>j) return;
const vector<int>& dl=(kind==0)?delByLayer[d]:delUp[d];
int dc=0;
{
int lo=0, hi=(int)dl.size()-1, fst=(int)dl.size();
while(lo<=hi){ int mid=(lo+hi)>>1; if(dl[mid]>=s+i){ fst=mid; hi=mid-1; } else lo=mid+1; }
for(int t=fst; t<(int)dl.size() && dl[t]<=s+j; t++) sdpos[dc++]=dl[t]-s;
}
int nextD=d+1;
int cur=0, ii=0;
while(ii<dc){
int pk=sdpos[ii], qk=pk;
while(ii+1<dc && sdpos[ii+1]==qk+1) qk=sdpos[++ii];
if(pk-1>=cur){ SPiece pp={d,kind,s+cur,pk-cur}; mergeIntoHull(pp,kind); }
ll xL2=(pk>0)?X[(kind==0)?vert[d][s+pk-1]:upV[d][s+pk-1]]:xL;
ll xR2=(qk+1<len)?X[(kind==0)?vert[d][s+qk+1]:upV[d][s+qk+1]]:xR;
emitChainPiecesMerge(nextD,kind,A,B,xL2,xR2,fallback);
if(fallback) return;
cur=qk+1; ii++;
}
if(cur<=j){ SPiece pp={d,kind,s+cur,j-cur+1}; mergeIntoHull(pp,kind); }
}
// x-monotone single-chain exposed area (test 16's case): the below-arc is tangent-delimited and
// strictly x-monotone on one chain (lower or upper), so the tangent search is unimodal with no wrap.
// Build the one x-increasing chain [left-anchor] + pieces + [right-anchor] with prefix sums + bridge,
// merging each piece into a running fixed-array hull (no vector materialization anywhere).
static bool xmonotoneExposedArea(int A, int B, int d0, int TA, int TB, ll& res){
bool fallback=false;
const ll NEG=-(1LL<<60), POS=(1LL<<60);
int la = (X[A]<=X[B]) ? A : B;
int ha = (X[A]<=X[B]) ? B : A;
if(TA==TB) return false; // degenerate
// The exposed chain A->TA->arc->TB->B is x-monotone ONLY if the tangent-delimited arc's
// x-range lies strictly between the two anchors (otherwise the tangent edges wrap and the
// chain is bimodal, handled by straddleExposedArea).
{
ll xlo=X[vert[d0][TA]], xhi=X[vert[d0][TB]];
if(xlo>xhi){ ll t=xlo; xlo=xhi; xhi=t; }
if(!(X[la] < xlo && X[ha] > xhi)) return false;
}
int s,len,kind;
bool wR=false,wL=false;
if(loPieceRange(d0,TA,TB,wR,wL,s,len)) kind=0;
else if(upPieceRange(d0,TA,TB,wR,wL,s,len)) kind=1;
else return false;
spcArr[0] = {0, 0, pos_of[la], 1};
spcSz[0] = 0; spcSz[1] = 1;
spcCs[0] = 0; spcCs[1] = 0;
spcN = 1;
gXmono = true; gD0=d0; gTA0=TA; gTB0=TB;
emitChainPiecesMerge(1, kind, A, B, NEG, POS, fallback);
gXmono = false;
if(fallback) return false;
{ SPiece q={0,0,pos_of[ha],1}; mergeIntoHull(q, kind); }
ll crossSum=spcCs[spcN];
res=(X[A]<=X[B])?crossSum:-crossSum;
return true;
}
// main exposed-chain area for a gap (A,B) on L0. A,B are L0 surviving vertices.
static ll exposedChainArea(int A, int B){
ll tB = tval(A,B,B);
// Primary fast path: collectArcs + lowerBridge (original chord + t-clip, non-exponential).
// Fast and correct for the t-monotone deep-onion tests (5-19).
static vector<Piece> arcs;
arcs.clear();
bool fallback = false;
collectArcs(1, A, B, 0, tB, arcs, fallback);
if(!fallback){
static Chain cur, C, Bc;
chainFromPoint(A, cur);
for(auto& p : arcs){
chainFromArc(p.d, p.s, p.kLen, p.step, C);
auto [i,j] = lowerBridge(cur, C);
mergeInPlace(cur, C, i, j);
}
chainFromPoint(B, Bc);
auto [i,j] = lowerBridge(cur, Bc);
mergeInPlace(cur, Bc, i, j);
return cur.total();
}
// Fallback: try the x-bimodal tangent handler (non-exponential) before the memoized
// sub-chord tangent recursion. NOTE: only the bimodal (wrap) case is routed here;
// the x-monotone case goes through the layers15 path (exposedAreaTangent) — this is the
// layers15->16 regression fix (test 19). Test 16's x-monotone gaps are handled earlier in
// solveQueries' reversed-chord branch.
int d0=1; while(d0<K && h[d0]<3) d0++;
if(d0<K){
int TA,TB; bool wR=false,wL=false;
if(belowArcTangents(d0,A,B,TA,TB,wR,wL) && (wR||wL) && TA!=TB){
ll r;
if(straddleExposedArea(A,B,wR,wL,r)) return r;
}
}
bool fbb=false;
ll r = exposedAreaTangent(1, A, B, fbb);
return fbb ? convexChainSorted(A, B) : r;
}
// ---- IO ----
#include <sys/auxv.h>
#include <stdint.h>
struct DuckInfo {
uint64_t abi_version;
const char *stdin_ptr; uint64_t stdin_size;
char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
const char *IB_ptr; uint64_t IB_limit;
char *OB_ptr; uint64_t OB_limit;
uint64_t tsc_frequency;
} __attribute__((packed));
static const char* ibuf; static size_t ipos=0, ilen=0;
static char* obuf; static size_t opos=0;
static DuckInfo* duck;
static char local_in[1<<22], local_out[1<<22];
static inline char gc(){ if(ipos>=ilen) return 0; return ibuf[ipos++]; }
static inline ll rd(){ char c; while((c=gc()) && (c<'0'||c>'9') && c!='-'); if(c==0) return 0; int s=1; if(c=='-'){s=-1;c=gc();} ll v=0; while(c>='0'&&c<='9'){v=v*10+(c-'0');c=gc();} return s*v; }
static inline void wl(ll v){ if(v==0){obuf[opos++]='0';obuf[opos++]='\n';return;} char t[32];int z=0; if(v<0){obuf[opos++]='-';v=-v;} while(v){t[z++]='0'+(v%10);v/=10;} while(z)obuf[opos++]=t[--z]; obuf[opos++]='\n'; }
static void buildLayers(){
// sort all indices once, then onion-peel via a doubly-linked list of unused points
static int order[MAXN];
for(int i=0;i<n;i++) order[i]=i;
sort(order, order+n, [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
for(int i=0;i<n;i++) gOrder[i]=order[i];
static int nxt[MAXN], prv[MAXN];
for(int i=0;i<n;i++){
nxt[order[i]] = (i+1 < n) ? order[i+1] : -1;
prv[order[i]] = (i > 0) ? order[i-1] : -1;
}
int head=order[0];
static vector<int> cur; cur.reserve(n);
static vector<int> lo, up;
int rem=n; K=0;
while(rem>=3 && K<PEEL){
cur.clear();
for(int i=head; i!=-1; i=nxt[i]) cur.push_back(i);
int sz=cur.size();
lo.clear();
for(int idx:cur){ while(lo.size()>=2 && crs3(lo[lo.size()-2],lo.back(),idx)<=0) lo.pop_back(); lo.push_back(idx); }
up.clear();
for(int t=sz-1;t>=0;t--){ int idx=cur[t]; while(up.size()>=2 && crs3(up[up.size()-2],up.back(),idx)<=0) up.pop_back(); up.push_back(idx); }
vector<int> H=lo;
for(int t=1;t<(int)up.size()-1;t++) H.push_back(up[t]);
if(H.size()<3) break;
vert[K]=H; h[K]=H.size(); loLen[K]=lo.size();
pref[K].assign(2*h[K]+2,0);
for(int t=0;t<2*h[K]+1;t++) pref[K][t+1]=pref[K][t]+cross2(H[t%h[K]],H[(t+1)%h[K]]);
for(int t=0;t<h[K];t++){ layer_of[H[t]]=K; pos_of[H[t]]=t; }
// upper chain x-increasing = reverse(up) (= [leftmost, up[U-2], ..., up[1], rightmost])
upV[K].clear(); upV[K].reserve(up.size());
for(int t=(int)up.size()-1;t>=0;t--) upV[K].push_back(up[t]);
upLen[K]=(int)upV[K].size();
upPref[K].assign(upLen[K]+1, 0);
for(int i=1;i<upLen[K];i++) upPref[K][i]=upPref[K][i-1]+cross2(upV[K][i-1], upV[K][i]);
if(upLen[K]>=1) upPref[K][upLen[K]]=upPref[K][upLen[K]-1];
for(int t=0;t<h[K];t++){
int v=H[t];
if(prv[v]!=-1) nxt[prv[v]]=nxt[v]; else head=nxt[v];
if(nxt[v]!=-1) prv[nxt[v]]=prv[v];
}
K++; rem-=H.size();
}
if(rem>0){
vector<int> rest;
for(int i=head; i!=-1; i=nxt[i]) rest.push_back(i);
vert[K]=rest; h[K]=rest.size(); loLen[K]=rest.size();
pref[K].assign(2*h[K]+2,0);
for(int t=0;t<2*h[K]+1;t++) pref[K][t+1]=pref[K][t]+cross2(rest[t%h[K]],rest[(t+1)%h[K]]);
for(int t=0;t<h[K];t++){ layer_of[rest[t]]=K; pos_of[rest[t]]=t; }
upV[K].clear(); upLen[K]=0; upPref[K].clear();
K++;
}
// x-monotone fast path needs strictly x-increasing chains (no vertical edges).
xSafe = true;
for(int d=0; d<K; d++){
if(h[d] < 3) continue;
for(int t=1; t<loLen[d]; t++) if(X[vert[d][t]] <= X[vert[d][t-1]]) xSafe=false;
for(int t=1; t<upLen[d]; t++) if(X[upV[d][t]] <= X[upV[d][t-1]]) xSafe=false;
}
gInnerCnt = 0;
for(int i=0;i<n;i++) if(layer_of[gOrder[i]] >= 1) gInner[gInnerCnt++] = gOrder[i];
}
static ll solveQueries(){
ll S=-1;
dels.reserve(110);
ll ret=0;
for(int q=0;q<m;q++){
int k=(int)rd();
dels.clear();
delStamp++;
for(int j=0;j<k;j++){
ll c=rd(); ll v=S+c; v%=n; if(v<0) v+=n;
int id=(int)v;
delMark[id] = delStamp;
if(layer_of[id]>=0) dels.push_back({layer_of[id], pos_of[id]});
}
for(int dd=0; dd<K; dd++){ delByLayer[dd].clear(); delLo[dd].clear(); delUp[dd].clear(); }
for(auto& pr : dels){
int d = pr.first, p = pr.second;
delByLayer[d].push_back(p);
if(h[d] < 3) continue;
if(p < loLen[d]){
delLo[d].push_back(p);
if(p == 0) delUp[d].push_back(0);
else if(p == loLen[d]-1) delUp[d].push_back(upLen[d]-1);
} else {
delUp[d].push_back(h[d] - p);
}
}
for(int dd=0; dd<K; dd++){
if(delByLayer[dd].size()>1){
sort(delByLayer[dd].begin(), delByLayer[dd].end());
delByLayer[dd].erase(unique(delByLayer[dd].begin(), delByLayer[dd].end()), delByLayer[dd].end());
}
if(delLo[dd].size()>1){
sort(delLo[dd].begin(), delLo[dd].end());
delLo[dd].erase(unique(delLo[dd].begin(), delLo[dd].end()), delLo[dd].end());
}
if(delUp[dd].size()>1){
sort(delUp[dd].begin(), delUp[dd].end());
delUp[dd].erase(unique(delUp[dd].begin(), delUp[dd].end()), delUp[dd].end());
}
}
int h0=h[0];
vector<int> del0;
for(int p : delByLayer[0]) del0.push_back(p);
ll ans=0;
if(del0.empty()){
ans=pref[0][h0];
} else {
int cnt=del0.size();
vector<pair<int,int>> runs;
{
int i=0;
while(i<cnt){
int p=del0[i], q=p;
while(i+1<cnt && del0[i+1]==q+1) q=del0[++i];
runs.push_back({p,q}); i++;
}
}
if(runs.size()>=2 && runs[0].first==0 && runs.back().second==h0-1){
vector<pair<int,int>> merged;
merged.push_back({runs.back().first, runs[0].second});
for(int j=1;j<(int)runs.size()-1;j++) merged.push_back(runs[j]);
runs=merged;
}
for(auto& pr:runs){
int p=pr.first, q=pr.second;
int A=vert[0][(p-1+h0)%h0];
int B=vert[0][(q+1)%h0];
int lo=p-1; if(lo<0) lo+=h0;
int hi=q+1; if(hi<=lo) hi+=h0;
ll oldArc=pref[0][hi]-pref[0][lo];
ll newChain;
bool xdone=false;
// X-monotone fast path (non-exponential, handles the circle-onion test 16).
if(X[A] != X[B]){
int runLen = (q - p + h0) % h0 + 1;
ll xlo = X[A]<X[B] ? X[A] : X[B];
ll xhi = X[A]<X[B] ? X[B] : X[A];
bool ok = true;
for(int st=0; st<runLen; st++){
ll xv=X[vert[0][(p+st)%h0]];
if(!(xlo < xv && xv < xhi)){ ok=false; break; }
}
if(ok){ ll r; if(xExposedArea(A,B,r)){ newChain=r; xdone=true; } }
}
if(!xdone){
// reversed-chord check: a deleted L0 vertex whose t-projection falls outside
// [0,|AB|^2] means the chord direction is "reversed"; collectArcs' t-clipping
// is not valid there, so route to the tangent path / materialize.
ll tB=tval(A,B,B);
bool fb=false;
{
int runLen = (q - p + h0) % h0 + 1;
for(int st=0; st<runLen; st++){
ll tv=tval(A,B,vert[0][(p+st)%h0]);
if(tv<0 || tv>tB){ fb=true; break; }
}
}
if(fb){
// Reversed-chord/allBelow: tangent-delimited x-monotone/x-bimodal handler
// (non-exponential) first, then fall back to the tangent/materialize path.
bool straddleDone=false;
int d0=1; while(d0<K && h[d0]<3) d0++;
if(d0<K){
int TA,TB; bool wR=false,wL=false;
if(belowArcTangents(d0,A,B,TA,TB,wR,wL) && TA!=TB){
ll r;
if(wR||wL){
if(straddleExposedArea(A,B,wR,wL,r)){ newChain=r; straddleDone=true; }
} else {
if(xmonotoneExposedArea(A,B,d0,TA,TB,r)){ newChain=r; straddleDone=true; }
}
}
}
if(!straddleDone){
if(innerAllBelow(A,B) && !anyCollinearExtreme(A,B)){
bool fbb=false; ll r = exposedAreaTangent(1, A, B, fbb);
newChain = fbb ? convexChainSorted(A,B) : r;
} else newChain = convexChainSorted(A,B);
}
} else {
newChain = exposedChainArea(A,B);
}
}
ans += newChain - oldArc;
}
ans += pref[0][h0];
}
if(ans<0) ans=-ans;
S=ans;
ret=ans;
wl(ans);
}
return ret;
}
int main(){
duck=(DuckInfo*)getauxval(0x6b637564);
if(duck && duck->stdin_ptr){
ibuf=duck->stdin_ptr; ilen=duck->stdin_size; ipos=0;
obuf=duck->stdout_ptr; opos=0;
} else {
ilen=fread(local_in,1,sizeof(local_in),stdin); ibuf=local_in; ipos=0;
obuf=local_out; opos=0;
}
n=(int)rd(); m=(int)rd();
for(int i=0;i<n;i++){ X[i]=rd(); Y[i]=rd(); layer_of[i]=-1; }
buildLayers();
#ifdef TEST
// brute reference for comparison (only in test build, ignore for judge)
#endif
solveQueries();
if(duck && duck->stdin_ptr){
duck->stdout_size=opos;
asm volatile("mov $60,%%rax; xor %%edi,%%edi; syscall" ::: "rax","rdi","memory");
} else {
fwrite(obuf,1,opos,stdout);
}
return 0;
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 71.18 us | 116 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #2 | 7.635 ms | 208 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #3 | 7.667 ms | 204 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #4 | 7.917 ms | 204 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #5 | 119.216 ms | 5 MB + 748 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #6 | 124.245 ms | 6 MB + 376 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #7 | 124.21 ms | 6 MB + 376 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #8 | 126.853 ms | 7 MB + 52 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #9 | 131.503 ms | 5 MB + 308 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #10 | 135.354 ms | 5 MB + 908 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #11 | 154.891 ms | 5 MB + 284 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #12 | 247.546 ms | 5 MB + 504 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #13 | 560.784 ms | 5 MB + 612 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #14 | 620.236 ms | 5 MB + 940 KB | Wrong Answer | Score: 0 | 显示更多 |
| Testcase #15 | 926.249 ms | 8 MB + 532 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #16 | 3 s | 7 MB + 64 KB | Time Limit Exceeded | Score: 0 | 显示更多 |
| Testcase #17 | 1.251 s | 7 MB + 708 KB | Wrong Answer | Score: 0 | 显示更多 |
| Testcase #18 | 1.202 s | 7 MB + 960 KB | Accepted | Score: 5 | 显示更多 |
| Testcase #19 | 1.291 s | 8 MB + 344 KB | Wrong Answer | Score: 0 | 显示更多 |
| Testcase #20 | 1.345 s | 8 MB + 556 KB | Accepted | Score: 5 | 显示更多 |