[luogu P2521] [HAOI2011]防线修建

时间:2021-10-21 13:11:36

[luogu P2521] [HAOI2011]防线修建

题目描述

近来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)和首都这三个城市是一定需要保护的。

[luogu P2521] [HAOI2011]防线修建(别瞅了,luogu没有图)

输入输出格式

输入格式:

第一行,三个整数n,x,y分别表示河边城市和首都是(0,0),(n,0),(x,y)。

第二行,一个整数m。

接下来m行,每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。

再接下来一个整数q,表示修改和询问总数。

接下来q行每行要么形如1 i,要么形如2,分别表示撤销第i个城市的保护和询问。

输出格式:

对于每个询问输出1行,一个实数v,表示修建防线的花费,保留两位小数

输入输出样例

输入样例#1: 复制
4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2
输出样例#1: 复制
6.47
5.84
4.47

说明

数据范围:

30%的数据m<=1000,q<=1000

100%的数据m<=100000,q<=200000,n>1

所有点的坐标范围均在10000以内, 数据保证没有重点

想了好久,也码了好久。刚开始没有想到时光倒流,往cdq去想了。平衡树也很难操作。

最后看了发题解——艹,怎么又没想到时光倒流!

时光倒流以后,就相当于维护一个支持单点更新的上凸包,并求周长-n。

还好题目限制好了,不然要烦死、、

那我们采取这样的方法:

插入一个点时,先判断在不在凸包内。如果不在,则向两边维护一个凸包,直到不能删点或者符合一个凸包时停止。

其中判断是否在凸包内,通过找两个点,一个前驱,一个后缀,都在凸包边上。

其中,设当前插入点为c,前缀为u,后缀为v,满足u.x<c.x||u.x==c.x&&u.y<c.y,v.x>c.x||v.x==c.x&&v.y>c.y。

如果cross(c-u,v-u)>0(cross表示两个向量叉积),则说明c在凸包内。

否则向两边维护更新凸壳。

根据对称性,我们只取向左边的进行研究。

设u为凸包上c的前缀,v为凸包上u的前缀。

当然如果u(0,0),那么就退出了,(0,0)是不能删的。

否则如果cross(c-v,u-v)>0,则维护好了,退出,否则就删了u,继续。

至此,维护单点更新成功了,且复杂度正确,因为,每个点最多插入一次,删除一次。

其中求pre,suc可以看做是连带的,换句话说,次数和删除操作次数差不多(倍数在常数级)。

这里的复杂度大致就是nlogn基本的。

但是同样,我们会有一个棘手的问题->计算周长。

如果每次找凸包上每个点的前驱后缀计算感觉会很慢,也很难写。

如果我们在删点,加点时就计算,是不是就比较快呢?

不过要注意,不要漏删一条边或多加一条边,细节还是有点的。

还有,其中前驱后缀插入删除都是平衡树的操作。

(splay比stl快?无意抢了luogu'rank1,233)

code:

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <cmath>
 #define ms(a,x) memset(a,x,sizeof a)
 using namespace std;

 void OJ() {
     #ifndef ONLINE_JUDGE
         freopen("in.txt","r",stdin);
         freopen("out.txt","w",stdout);
     #endif
 }
 namespace fastIO {
     #define gec(c) getchar(c)
     #define puc(c) putchar(c)
     char ch;
     inline int read() {
         ,f=; ch=getchar();
         ') {
             if (ch=='-') f=-f;
             ch=gec();
         }
         ') {
             x=(x<<)+(x<<)+ch-';
             ch=getchar();
         }
         return x*f;
     }
 } using namespace fastIO;

 ;
 int n,m,q,las;
 bool vis[N]; double ans[N];
 struct query {
     int t,x;
 } o[N];

 #define SplayTree node
 struct SplayTree {
     int X,Y;
     node* c[];
     node () {
         X=Y=;
         c[]=c[]=c[]=;
     }
 } * ro,* g,* U,* V,* re;

 #define vec city
 struct city {
     int x,y;
     city () {}
     city (int _x,int _y) :
         x(_x),y(_y) {};
     city (node* u) :
         x(u->X),y(u->Y) {};
 } a[N];
 int cross (vec u,vec v) {
     return u.x*v.y-u.y*v.x;
 }
 vec operator - (city u,city v) {
     return vec(u.x-v.x,u.y-v.y);
 }
 node* noded (city u) {
     node* rt=new node();
     rt->X=u.x,rt->Y=u.y;
     return rt;
 }
 void setup (node* &x,int X,int Y) {
     x=new node(),x->X=X,x->Y=Y;
 }
 bool dir (node* x) {
     ]) ;
     ]->c[]==x;
 }
 void linknode (node* y,node* x,bool p) {
     ]=y;
     if (y) y->c[p]=x;
 }
 void rotate (node* x) {
     ];
     linknode(y->c[],x,dir(y));
     linknode(y,x->c[p^],p);
     linknode(x,y,p^);
 }
 void splay (node* x,node* an) {
     ]==an) return;
     ]!=an) {
         ]->c[]==an) {
             rotate(x);
             if (!an) ro=x;
             return;
         }
         rotate(dir(x)^dir(x->c[])?x:x->c[]);
         rotate(x);
     }
     if (!an) ro=x;
 }
 bool cmp (node* u,node* v) {
     return u->X==v->X?u->Y<v->Y:u->X<v->X;
 }
 void insert (node* &x,node* u) {
     if (!x) {
         g=x=u;
         return;
     }
     bool p=cmp(x,u);
     insert(x->c[p],u),x->c[p]->c[]=x;
 }
 void erase (node* u) {
     splay(u,);
     ]||!ro->c[]) {
         ]) ro=ro->c[],ro->c[]=; else
         ]) ro=ro->c[],ro->c[]=; else
         ro=;
         return;
     }
     ]; re->c[]; re=re->c[]) ;
     splay(re,ro);
     re->c[]=,re->c[]=ro->c[];
     ]) re->c[]->c[]=re;
     ro=re;
 }
 bool cmp_1 (node* u,node* v) {
     return u->X==v->X?u->Y<v->Y:u->X<v->X;
 }
 bool cmp_2 (node* u,node* v) {
     return u->X==v->X?u->Y>v->Y:u->X>v->X;
 }
 void pre (node* x,node* u) {
     if (!x) return;
     ],u);
     ],u);
 }
 void suc (node* x,node* u) {
     if (!x) return;
     ],u);
     ],u);
 }
 #define sqr(x) ((x)*(x))
 double dis (node* u,node* v) {
     return sqrt(sqr(u->X-v->X)+sqr(u->Y-v->Y));
 }
 void maintain () {
     pre(ro,g),U=re,suc(ro,g),V=re;
     ) return;
     ||U->Y!=||V->X!=n||V->Y!=) ans[]-=dis(U,V);
     for ( ; ; ) {
         pre(ro,g),U=re;
         &&U->Y==) {
             ans[]+=dis(g,U);
             break;
         }
         pre(ro,U),V=re;
         ) {
             ans[]+=dis(g,U);
             break;
         }
         ans[]-=dis(U,V);
         erase(U);
     }
     for ( ; ; ) {
         suc(ro,g),U=re;
         ) {
             ans[]+=dis(g,U);
             break;
         }
         suc(ro,U),V=re;
         ) {
             ans[]+=dis(g,U);
             break;
         }
         ans[]-=dis(U,V);
         erase(U);
     }
     insert(ro,g);
     splay(g,);
 }

 int main() {
     OJ();
     n=read(),a[].x=read(),a[].y=read();
     m=read(),a[m+]=city(,),a[m+]=city(n,);
     ; i<=m; ++i) {
         a[i].x=read(),a[i].y=read();
     }
     ms(vis,);
     q=read();
     ; i<=q; ++i) {
         o[i].t=read();
         ) o[i].x=read();
         vis[o[i].x]=;
     }
     ro=;
     insert(ro,noded(a[]));
     insert(ro,noded(a[m+]));
     insert(ro,noded(a[m+]));
     ans[]=dis(noded(a[]),noded(a[m+]))+dis(noded(a[]),noded(a[m+]));
     ; i<=m; ++i) {
         if (vis[i]) g=noded(a[i]),maintain();
     }
     for (int i=q; i; --i) {
         ) g=noded(a[o[i].x]),maintain();
         ];
     }
     ; i<=q; ++i) {
         ) printf("%.2lf\n",ans[i]);
     }
     ;
 }

[luogu P2521] [HAOI2011]防线修建的更多相关文章

  1. P2521 &lbrack;HAOI2011&rsqb;防线修建

    题目链接:P2521 [HAOI2011]防线修建 题意:给定点集 每次有两种操作: 1. 删除一个点 (除开(0, 0), (n, 0), 与指定首都(x, y)) 2. 询问上凸包长度 至于为什么 ...

  2. 【题解】P2521 &lbrack;HAOI2011&rsqb;防线修建&lpar;动态凸包&rpar;

    [题解]P2521 [HAOI2011]防线修建(动态凸包) 凸包是易插入不好删除的东西,按照剧情所以我们时光倒流 然后问题就是维护凸包的周长,支持加入 本来很简单,但是计算几何就是一些小地方经验不足 ...

  3. Bzoj2300 &sol; 洛谷P2521 &lbrack;HAOI2011&rsqb;防线修建

    题目描述 近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了.可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于 ...

  4. 【BZOJ 2300】 2300&colon; &lbrack;HAOI2011&rsqb;防线修建 (动态凸包&plus;set)

    2300: [HAOI2011]防线修建 Description 近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了.可是A国上 ...

  5. BZOJ 2300&colon; &lbrack;HAOI2011&rsqb;防线修建&lpar; 动态凸包 &rpar;

    离线然后倒着做就变成了支持加点的动态凸包...用平衡树维护上凸壳...时间复杂度O(NlogN) --------------------------------------------------- ...

  6. bzoj千题计划236:bzoj2300&colon; &lbrack;HAOI2011&rsqb;防线修建

    http://www.lydsy.com/JudgeOnline/problem.php?id=2300 维护动态凸包,人懒用的set 用叉积判断,不要用斜率 #include<set> ...

  7. 【BZOJ2300】&lbrack;HAOI2011&rsqb;防线修建 set维护凸包

    [BZOJ2300][HAOI2011]防线修建 Description 近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了.可 ...

  8. 【bzoj2300】【Luogu P2521】 &lbrack;HAOI2011&rsqb;防线修建 动态凸包,平衡树,Set

    一句话题意:给你一个凸包,每次可以插入一个点或者询问周长. 动态凸包裸题嘛,用\(Set\)实现.最初每个点坐标做乘三处理,便于取初始三角形的重心作为凸包判定原点. #include <bits ...

  9. BZOJ2300&lbrack;HAOI2011&rsqb;防线修建——非旋转treap&plus;凸包&lpar;平衡树动态维护凸包&rpar;

    题目描述 近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了.可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于 ...

随机推荐

  1. POJ 2115 C Looooops扩展欧几里得

    题意不难理解,看了后就能得出下列式子: (A+C*x-B)mod(2^k)=0 即(C*x)mod(2^k)=(B-A)mod(2^k) 利用模线性方程(线性同余方程)即可求解 模板直达车 #incl ...

  2. mvc配合jquery&period;validate验证失效&comma;情况之一

    用viewbage绑定input空间的value值,通过submit提交.validate验证失效. 1.应该是mvc的渲染顺序导致js验证失败. 解决方案:改用mvc自带的@html辅助方法,生成文 ...

  3. js实现拖拽

    拖拽:最核心是三个事件,鼠标按下,鼠标移动,鼠标弹起.按下时激活拖拽,然后时刻根据鼠标的位置来更新物体的left和top值,达到跟随鼠标的效果,鼠标弹起则取消拖拽. 以下是代码: <!DOCTY ...

  4. qunit&period;js初试

    看了下mbraak-simple-data-grid写的单元测试,感觉还是很好入手的 用module函数定义模块 用test函数定义测试方法 用equal.ok(判断是否为真)等方法做断言判断 用se ...

  5. 安全-分析深圳电信的新型HTTP劫持方式

    ISP的劫持手段真是花样百出,从以前的DNS(污染)劫持到后来的共享检测,无不通过劫持正常的请求来达到他们的目的. 之前分析过通过劫持HTTP会话,插入iframe来检测用户后端有无共享行为,但后来移 ...

  6. python杂记-5&lpar;装饰器&rpar;

    1.被装饰的函数有参数(一个参数): def w1(func): def inner(arg): # 验证1 # 验证2 # 验证3 return func(arg) return inner @w1 ...

  7. Excel设置数据有效性实现单元格下拉菜单的3种方法&lpar;转)

    http://blog.csdn.net/cdefu/article/details/4129136 一.直接输入: 1.选择要设置的单元格,譬如A1单元格: 2.选择菜单栏的“数据”→“有效性”→出 ...

  8. 学习笔记之Lucene

    http://baike.baidu.com/view/371811.htm?fr=aladdin Apache Lucene(http://lucene.apache.org/) Java 全文搜索 ...

  9. HNCU1099:堆积木

    http://hncu.acmclub.com/index.php?app=problem_title&id=111&problem_id=1099 题目描述 小明的侄子要过生日了,小 ...

  10. Verilog HDL程序设计——基本要素

    Verilog基本上熟悉了,继续整理一下Verilog的学习笔记吧.前面记载了Verilog的结构,写Verilog的结构有了,但是该怎么写呢?在写之前就得了解一下Verilog的一些基本要素了,也就 ...