bzoj 2300 动态维护上凸壳（不支持删除）

新技能GET。

用set保存点，然后只需要找前趋和后继就可以动态维护了。

 /**************************************************************

     Problem: 2300

     User: idy002

     Language: C++

     Result: Accepted

     Time:556 ms

     Memory:4824 kb

 ****************************************************************/

 #include <cstdio>

 #include <cmath>

 #include <set>

 #define N 100010

 #define line(a,b) ((b)-(a))

 using namespace std;

 struct Job {

     int opt, v;

     double ans;

 };

 struct Vector {

     int x, y;

     void read() { scanf( "%d%d", &x, &y ); }

     Vector(){}

     Vector( int x, int y ):x(x),y(y){}

     Vector operator+( const Vector &b ) const { return Vector(x+b.x,y+b.y); }

     Vector operator-( const Vector &b ) const { return Vector(x-b.x,y-b.y); }

     int operator^( const Vector &b ) const { return x*b.y-y*b.x; }

     double len() { return sqrt(x*x+y*y); }

     bool operator<( const Vector &b ) const {

         return x<b.x || (x==b.x && y<b.y);

     }

 };

 typedef Vector Point;

 int n, m, q;

 Point pts[N];

 set<Point> cvx;

 Job job[N+N];

 bool done[N];

 double ans;

 bool onleft( const Point &a, const Point &b, const Point &c ) {

     return (line(a,b) ^ line(a,c)) > ;

 }

 void insert( const Point &p ) {

     set<Point>::iterator prv, nxt, prev, next;

     prv = nxt = cvx.upper_bound( p );

     --prv;

     if( !onleft(*nxt,p,*prv) ) return;

     while( prv!=cvx.begin() ) {

         prev = prv;

         --prev;

         if( !onleft(p,*prv,*prev) ) {

             ans += line(*prev,*nxt).len()-line(*prev,*prv).len()-line(*prv,*nxt).len();

             cvx.erase(prv);

         } else break;

         prv = prev;

     }

     while( nxt!=cvx.end() ) {

         next = nxt;

         ++next;

         if( next==cvx.end() ) break;

         if( !onleft(*next,*nxt,p) ) {

             ans += line(*prv,*next).len()-line(*prv,*nxt).len()-line(*nxt,*next).len();

             cvx.erase(nxt);

         } else break;

         nxt = next;

     }

     cvx.insert( p );

     ans += line(*prv,p).len()+line(*nxt,p).len()-line(*prv,*nxt).len();

 }

 int main() {

     scanf( "%d", &n );

     pts[].read();

     scanf( "%d", &m );

     for( int i=; i<=m; i++ )

         pts[i].read();

     scanf( "%d", &q );

     for( int i=; i<=q; i++ ) {

         scanf( "%d", &job[i].opt );

         if( job[i].opt== ) {

             scanf( "%d", &job[i].v );

             done[job[i].v] = true;

         }

     }

     cvx.insert( Point(,) );

     cvx.insert( pts[] );

     cvx.insert( Point(n,) );

     ans += line(Point(,),pts[]).len() + line(Point(n,),pts[]).len();

     for( int i=; i<=m; i++ )

         if( !done[i] ) insert( pts[i] );

     for( int i=q; i>=; i-- ) {

         if( job[i].opt== ) {

             insert( pts[job[i].v] );

         } else {

             job[i].ans = ans;

         }

     }

     for( int i=; i<=q; i++ )

         if( job[i].opt== )

             printf( "%.2lf\n", job[i].ans );

 }