#题目描述
近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务:
- 给出你所有的A国城市坐标
- A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了
- 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;
}