首页 > 其他分享 >题解:P2521 [HAOI2011] 防线修建

题解:P2521 [HAOI2011] 防线修建

时间:2024-08-25 21:04:02浏览次数:12  
标签:return HAOI2011 题解 凸包 int vec auto y0 P2521

题意

给定若干个点,实现下列操作:

  • 删除一个点。
  • 查询上凸包的周长。

分析

建议先完成【模板】二维凸包

对于这个删除操作,我们没有好的方法去在线维护它。

考虑离线询问。

这样删除操作就变成了插入操作。


插入一个新点有如下两种情况:

  • 新点在凸包内。
  • 新点在凸包外。

我们回忆一下 Andrew 算法的过程:先将点按 \(x\) 排序,然后单调栈维护凸包。

这给了我们启示,如果一个点 \((x_i,y_i)\) 能加入凸包中,那么原凸包中和直线 \(x=x_i\) 相交的边一定被删除。

将原点集按 \(x\) 排序,这条边连接的两个点显然就是 \((x_i,y_i)\) 的前驱和后继。

考虑用平衡树维护,判断点 \((x_i,y_i)\) 与该边的位置关系即可。

在凸包内那么就不用更新凸包。


考虑该点在凸包外的情况。

我们先将该点加入凸包并更新答案。

我们从该点出发,向前后分别扫一遍,将不符合凸包性质的点删除并更新答案。

如果一个点符合凸包性质,那么显然它前或后的点也满足凸包性质,就结束循环。

每个点最多进一次凸包点集,也最多出一次凸包点集,时间复杂度 \(O(m\log m)\)。

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005

struct vec
{
    double x, y;
    vec(double X=0, double Y=0): x(X), y(Y) {}
    friend vec operator-(vec a, vec b) {return {a.x-b.x, a.y-b.y};    }
    friend int cross    (vec a, vec b) {return a.x*b.y-a.y*b.x;       }
    auto operator<=>    (vec b) const  {return x==b.x?y<=>b.y:x<=>b.x;}
    double length       ()             {return sqrt(x*x+y*y);         }
};

set<vec> s;
double ans;

bool chk(vec A)
{
    auto it=s.lower_bound(A);
    vec B=*it, C=*--it;
    return cross(B-A, B-C)<=0;
}

auto pre(set<vec>::iterator it) {return --it;}
auto aft(set<vec>::iterator it) {return ++it;}

bool erase(set<vec>::iterator it)
{
    if(it==s.begin()) return 0;
    auto itl=pre(it);
    auto itr=aft(it);
    if(itr==s.end()) return 0;
    vec a=*it-*itl, b=*itr-*it;
    if(cross(a, b)<0) return 0;
    ans+=(*itr-*itl).length()-a.length()-b.length();
    s.erase(it);
    return 1;
    
}

void insert(vec A)
{
    if(chk(A)) return;
    auto it=s.insert(A).first;
    auto pr=pre(it);
    auto af=aft(it);
    ans+=(*it-*pr).length()+(*it-*af).length()-(*af-*pr).length();
    while(erase(pre(it)));
    while(erase(aft(it)));
}

vector<pair<int, int>> vc;
vec dts[maxn];
bool del[maxn];
vector<double> Ans;

int main()
{
    int n, m, x0, y0;
    cin>>n>>x0>>y0>>m;
    for(int i=1;i<=m;i++) 
        cin>>dts[i].x>>dts[i].y;
    int q;
    cin>>q;
    for(int i=1, op, x=0;i<=q;i++)
    {
        cin>>op;
        if(op==1) cin>>x, del[x]=1;
        vc.emplace_back(op, x);
    }
    s.emplace(0, 0);
    s.emplace(n, 0);
    s.emplace(x0, y0);
    ans=vec(x0, y0).length()+vec(x0-n, y0).length();
    for(int i=1;i<=m;i++) if(!del[i]) insert(dts[i]);
    for(auto [op, x]:views::reverse(vc))
    {
        if(op==1) insert(dts[x]);
        else Ans.emplace_back(ans);
    }
    for(auto i:views::reverse(Ans)) 
        printf("%.2lf\n", i);
}

标签:return,HAOI2011,题解,凸包,int,vec,auto,y0,P2521
From: https://www.cnblogs.com/redacted-area/p/18379565

相关文章

  • 题解:CF235C Cyclical Quest
    题意给定一个主串\(S\)和\(n\)个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。分析后缀自动机好题。循环同构的过程可以看作从该串的头部删除一个字符,并在尾部加入一个字符。在后缀自动机上,跳parent树的过程就相当于删除头部的若干个字符。所以我们可......
  • 7z解压crc错误_7-Zip - 常见问题解答
    7z解压crc错误_7-Zip-常见问题解答7z解压crc错误_7-Zip-常见问题解答1.引言1.17-Zip简介1.2CRC错误概述2.7z文件和CRC错误2.1什么是7z文件2.2CRC错误的定义2.3CRC错误对文件的影响3.常见原因分析3.1文件传输过程中的错误3.2存储介质的损坏3.3不兼容的压......
  • 题解:P5680 [GZOI2017] 共享单车
    题目分析出题人是擅长隐藏题意的建树首先给你一张无向图,然后指定一个根节点\(k\),从根节点开始沿最短路到每一个节点。如果到某个节点有多条最短路径,选择上一个节点编号最短的。考虑记录前驱的Dijkstra。namespaceDJ{intdis[maxn],pre[maxn],val[maxn],vis[maxn]......
  • 题解:SP22382 ETFD - Euler Totient Function Depth
    题目链接:link,点击这里喵。前置知识:【模板】线性筛素数,欧拉函数,点击这里喵。题意简述:给定整数$l,r,k$,求出$[l,r]$中有多少个整数不断对自己取欧拉函数刚好$k$次结果为$1$。思路:看眼数据范围,$10^{10}$的量级显然不容我们每次暴力,故考虑预处理$\varphi(i),can(i,k),su......
  • 【面试系列】大数据平台常见面试题解答
    欢迎来到我的博客,很高兴能够在这里和您见面!欢迎订阅相关专栏:工......
  • AtCoder ABC 368题解
    前言本题解部分思路来自于网络。A-Cut题目大意有\(n\)张卡片叠在一起,从上到下给出\(n\)卡片的编号,将\(k\)张卡片从牌堆底部放到顶部后,从上到下输出卡片的编号。解题思路按照题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;inta[105];intmai......
  • SP666 VOCV - Con-Junctions 题解
    注意到这个问题具有最优子结构性,考虑树上dp。记$dp[i][0/1]$表示i号节点不放灯或放灯的最小值,$s[i][0/1]$为对应的方案数。那么我们可以进行如下转移:$dp[u][0]=\sum_{u->v}dp[v][1]$$dp[u][1]=\sum_{u->v}\min(dp[v][0],dp[v][1])$在更新对应的dp数组时,我们用......
  • P9482 [NOI2023] 字符串 题解
    题目描述\(T\)组数据,给定长为\(n\)的字符串\(s\),\(q\)次询问,给定\(i,r\),求有多少个\(l\)满足:\(1\lel\ler\)。\(s[i:i+l-1]\)字典序小于\(R(s[i+l:i+2l-1])\)。数据范围\(1\leT\le5,1\len,q\le10^5,1\lei+2r-1\len\)。时间限制\(\texttt{1s}\),......
  • Triple Attack 题解
    直接暴力显然不可行。我们容易发现,变量\(T\)的增量以\(3\)为循环,一次循环会造成\(5\)的贡献,所以我们容易想到对每个\(a_i\)直接对\(5\)计算倍数和取余,然后对于余数分类讨论去增加,然后对于倍数部分统一增加即可。有些细节。Code#include<bits/stdc++.h>//#include......
  • Minimum Steiner Tree 题解
    原题,详见P10723。几乎相同,我们只需要以一个需要选择的点为根,遍历子树看看有没有出现需要选择的点,然后直接去删除即可,可以看我的博客。但是我们也可以换一种做法,用类似拓扑排序的算法。先找到所有只连一条边且没有被选择的点,然后放进队列,接着依次取出队头遍历与它相连的点,同时记......