BZOJ2300/HAOI2011/防线修建

Posted on By 二价氢

#题目描述

近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务:

  1. 给出你所有的A国城市坐标
  2. A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了
  3. A国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少

你需要对每次询问作出回答。注意单位1长度的防线花费为1。

A国的地形是这样的,形如下图,x轴是一条河流,相当于一条天然防线,不需要你再修建

A国总是有两个城市在河边,一个点是(0,0),一个点是(n,0),其余所有点的横坐标均大于0小于n,纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。

上图中,A,B,C,D,E点为A国城市,且目前都要保护,那么修建的防线就会是A-B-C-D,花费也就是线段AB的长度+线段BC的长度+线段CD的长度

如果,这个时候撤销B点的保护,那么防线变成下图

#做法

我们将在线操作转换成离线操作,假设一开始只有这三个点

这时,加入一个点D,按照极(基)角排序后,它的前驱为点A,后继为点C,由于\(C\)在\(\vec{AD}\)的“右前”侧,因此直接将D压入凸包,答案减去\(AC\),加上\(AD+DC\)

这时,再加入一个点E,排序后,它的前驱为点D,后继为点C,由图可知,D、C都不应该在凸包上,因而将D,C删除,答案减去\(AD+DC+CB\),加上\(AE+EB\)

结果

#复杂度分析 \(O(N \log N)\)其中每个点访问一次,利用平衡树,每次压入、查询前驱、查询后继、删除操作都是\(O(\log N)\)的

#AC Code

使用std::multiset作为平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
//-- 浮点数运算
const double eps=1e-8;
bool _l (double a,double b){return a<b-eps;}
bool _g (double a,double b){return b<a-eps;}
bool _le(double a,double b){return a<b+eps;}
bool _ge(double a,double b){return b<a+eps;}
bool _eq(double a,double b){return fabs(a-b)<eps;}

const long long sqr(const long long &x){return x*x;}
//-- 点和向量
int n,x,y;
struct Point
{
    long long x,y;
    double angle;
    Point(){}
    Point(long long _x,long long _y):
        x(_x),y(_y),angle(atan2((double)y,(double)(x-n/2.0))){}
    void Init()
        {angle=atan2((double)y,(double)(x-n/2.0));}
    bool      operator == (const Point &a)const
        {return (a.x==x)&&(a.y==y);}
    bool      operator != (const Point &a)const
        {return !((*this)==a);}
    bool      operator <  (const Point &a)const
    {
        return
        (_l(angle,a.angle))||
        (_eq(angle,a.angle) && (sqr(x-n/2.0)+sqr(y)<sqr(a.x-n/2.0)+sqr(a.y)));
    }
    Point     operator -  (const Point &a)const
        {return Point(x-a.x,y-a.y);}
    long long operator *  (const Point &a)const
        {return x*a.y-y*a.x;}
    long long operator &  (Point a)
        {return x*a.x+y*a.y;}
    Point     operator ~  (void)
        {return Point(y,-x);}
};
//-- Line
struct Line
{
    Point a,b;
    Point operator * (Point p)
    {
        double x1 = a.x,x2=b.x,y1=a.y,y2=b.y;
        double A=y1-y2,B=x2-x1,C=x1*y2-x2*y1;
        double delta=(A*p.x+B*p.y+C)/(A*A+B*B);
        return Point(p.x-2*A*delta,p.y-2*B*delta);
    }
};
double dist(Point a,Point b){return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}
typedef Point Vector;
//-- 完毕

struct DymaicHull{
    multiset<Point>S;
    double ans;
    typedef multiset<Point>::iterator spci;
    bool IsOnSeg(const Point &u,const Point &v,const Point &w)
    {
        return ((u-w)*(v-w))==0 && ((u-w)&(v-w))<=0;
    }
    DymaicHull(Point a,Point b,Point x)
    {
        S.insert(a),S.insert(b),S.insert(x);
        ans=dist(a,b)+dist(a,x)+dist(b,x);
    }
    Point findNext(const Point &u)
    {
        spci it = S.upper_bound(u);
        if (it==S.end())
            it=S.begin();
        return *it;
    }
    Point findPre(const Point &u)
    {
        spci it=S.lower_bound(u);
        if (it==S.begin())
            it=S.end();
        it--;
        return *it;
    }
    bool IsInHull(const Point &u)
    {
        if (S.count(u)>0)
            return 1;
        Point t1=findNext(u),t2=findPre(u);
        long long k=((t1-u)*(t2-u));
        if (k<0 || (IsOnSeg(t1,t2,u)))
            return 1;
        return 0;
    }
    void insert(const Point &u)
    {
        if (IsInHull(u))
            return;
        while (1)
        {
            Point t1=findNext(u);
            Point t2=findNext(t1);
            Point t3=findPre(t1);
            long long k=(t2-u)*(t1-u);
            if (k>=0)
                S.erase(t1),ans-=dist(t3,t1)+dist(t1,t2)-dist(t2,t3);
            else
                break;
        }
        while (1)
        {
            Point t1=findPre(u);
            Point t2=findPre(t1);
            Point t3=findNext(t1);
            long long k=(t2-u)*(t1-u);
            if (k<=0)
                S.erase(t1),ans-=dist(t3,t1)+dist(t1,t2)-dist(t2,t3);
            else
                break;
        }
        Point t1=findPre(u);
        Point t2=findNext(u);
        ans-=dist(t1,t2);
        ans+=dist(t1,u)+dist(t2,u);
        S.insert(u);
    }
    double GetAns()
    {
        return ans;
    }
};
struct Query{
    int op,i;
    double ans;
};
const int maxm=100005,maxq=200005;
Point City[maxm];
Query Q[maxq];
bool Save[maxm];
int m,q;
int main()
{
    scanf("%d%d%d",&n,&x,&y);
    DymaicHull Sol(Point(0,0),Point(n,0),Point(x,y));
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&City[i].x,&City[i].y);
        Save[i]=true;
        City[i].Init();
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
    {
        scanf("%d",&Q[i].op);
        if (Q[i].op==1)
        {
            scanf("%d",&Q[i].i);
            Save[Q[i].i]=false;
        }
    }
    for (int i=1;i<=m;i++)
        if (Save[i])
            Sol.insert(City[i]);
    for (int i=q;i>=1;i--)
        if (Q[i].op==1)
            Sol.insert(City[Q[i].i]);
        else
            Q[i].ans=Sol.GetAns();
    for (int i=1;i<=q;i++)
        if (Q[i].op==2)
            printf("%.2lf\n",Q[i].ans-n);
    return 0;
}