倒序处理，只需要进行插入并维护凸包。用set按照 x <script type="math/tex" id="MathJax-Element-20">x</script>坐标维护点，每次先判断插入的点是否在凸包外部，然后删去两边被包含的点。
#include<cstdio> #include<cmath> #include<set> #include<algorithm> using namespace std; const int maxm=200010; int rd() { int x=0; char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x; } struct Vector { int x,y; bool operator < (const Vector &v) const { if (x!=v.x) return x<v.x; return y<v.y; } void read() { x=rd(); y=rd(); } Vector operator + (const Vector &v) const { return (Vector){x+v.x,y+v.y}; } Vector operator - (const Vector &v) const { return (Vector){x-v.x,y-v.y}; } }a[maxm]; typedef Vector Point; int dot(Vector v,Vector u) { return v.x*u.x+v.y*u.y; } int cross(Vector v,Vector u) { return v.x*u.y-v.y*u.x; } double dis(Point p,Point q) { return sqrt(dot(p-q,p-q)); } set<Point> s; set<Point>::iterator i1,i2,i3; int n,m,q,qk[maxm],qu[maxm],out[maxm]; double ans[maxm],now; void add(Point p) { i1=s.lower_bound(p); i2=i1; i2--; if (cross(*i1-*i2,p-*i2)<=0) return; now+=dis(p,*i1)+dis(p,*i2)-dis(*i1,*i2); s.insert(p); while (1) { i1=s.upper_bound(p); i2=i1; i2--; i2--; if (i2==s.begin()) break; i3=i2; i3--; if (cross(p-*i3,*i2-*i3)<=0) { now-=dis(p,*i2)+dis(*i2,*i3)-dis(p,*i3); s.erase(i2); } else break; } while (1) { i2=s.upper_bound(p); i3=i2; i3++; if (i3==s.end()) break; i1=i2; i1--; i1--; if (cross(p-*i3,*i2-*i3)>=0) { now-=dis(p,*i2)+dis(*i2,*i3)-dis(p,*i3); s.erase(i2); } else break; } } int main() { int x,y; s.insert((Point){0,0}); x=rd(); s.insert((Point){x,0}); x=rd(); y=rd(); s.insert((Point){x,y}); now=dis(*s.begin(),*(++s.begin()))+dis(*(++s.begin()),*(++(++s.begin()))); n=rd(); for (int i=1;i<=n;i++) a[i].read(); q=rd(); for (int i=1;i<=q;i++) { qk[i]=rd(); if (qk[i]==1) out[qu[i]=rd()]=1; } for (int i=1;i<=n;i++) if (!out[i]) add(a[i]); for (int i=q;i;i--) if (qk[i]==1) add(a[qu[i]]); else ans[i]=now; for (int i=1;i<=q;i++) if (qk[i]==2) printf("%.2f\n",ans[i]); }