首页 > 代码库 > BZOJ 2300 HAOI 2011 防线修建 动态维护凸包
BZOJ 2300 HAOI 2011 防线修建 动态维护凸包
题目大意:一些成熟分布在第一象限中,现在要建造一个防线来保护他们,但是随着时间的推移,必须要舍弃一些城市,但是不会舍弃首都。问最短的防线需要多长。
思路:在每一个时刻求一个上凸包就是答案了。当然这样做时间复杂度就呵呵了。考虑一下动态维护凸包。因为只有上凸包,所以处理起来会相对方便。我们只需把在凸包中的点按照x坐标排序,然后二分一下把点插入凸包,然后左右用斜率维护一下,这样每次插点的时间复杂度大概是O(logn)。但是这样只能插点不能删点,所以离线处理一下,把删点转化为插点,最后倒着输出。
(我比较懒,然后为省去平衡树直接上set了,可恶的iterator不支持+1,写的这个DT。。。
CODE:
#include <set> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 200010 #define EPS 1e-10 using namespace std; struct Operation{ int flag,p; void Read() { scanf("%d",&flag); if(flag == 1) scanf("%d",&p); } }opt[MAX]; struct Point{ int x,y; Point(int _ = 0,int __ = 0):x(_),y(__) {} bool operator <(const Point &a)const { if(x == a.x) return y < a.y; return x < a.x; } void Read() { scanf("%d%d",&x,&y); } }point[MAX]; set<Point> convex; set<Point>::iterator first,last; int cnt,asks; int x,y,n; bool ban[MAX]; double ans[MAX]; double length; inline double Calc(const Point &a,const Point &b) { return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y)); } inline double GetSlope(const Point &a,const Point &b) { if(a.x == b.x) return 1e15; return (double)(b.y - a.y) / (b.x - a.x); } inline void Insert(const Point &p) { set<Point>::iterator it = convex.insert(p).first; set<Point>::iterator _it = --it; ++it; set<Point>::iterator __it = first; if(_it != first) { __it = --_it; ++_it; } set<Point>::iterator it_ = ++it; --it; set<Point>::iterator it__ = last; if(it_ != last) { it__ = ++it_; --it_; } if(GetSlope(*_it,*it) > GetSlope(*it,*it_)) length -= Calc(*_it,*it_); else { convex.erase(it); return ; } while(_it != first && GetSlope(*__it,*_it) < GetSlope(*_it,*it)) { length -= Calc(*_it,*__it); convex.erase(_it); _it = __it--; } while(it_ != last && GetSlope(*it,*it_) < GetSlope(*it_,*it__)) { length -= Calc(*it_,*it__); convex.erase(it_); it_ = it__++; } length += Calc(*it,*_it) + Calc(*it,*it_); } int main() { cin >> n >> x >> y; first = convex.insert(Point(0,0)).first; convex.insert(Point(x,y)); last = convex.insert(Point(n,0)).first; length = Calc(Point(x,y),Point(0,0)) + Calc(Point(x,y),Point(n,0)); cin >> cnt; for(int i = 1; i <= cnt; ++i) point[i].Read(); cin >> asks; for(int i = 1; i <= asks; ++i) { opt[i].Read(); ban[opt[i].p] = true; } for(int i = 1; i <= cnt; ++i) if(!ban[i]) Insert(point[i]); for(int i = asks; i; --i) { if(opt[i].flag == 1) Insert(point[opt[i].p]); else ans[i] = length; } for(int i = 1; i <= asks; ++i) if(fabs(ans[i]) > EPS) printf("%.2lf\n",ans[i]); return 0; }
BZOJ 2300 HAOI 2011 防线修建 动态维护凸包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。