题意

给出

n

，在第一象限的一个稳定点和

m

个非稳定点（坐标保证

x\in (0,n),y \in (0,+\infin)

）。存在删除非稳定点的操作，问这些点和

(0,0),(0,n)

组成的凸包外周不与

x

轴重合的边的长度之和。

解法

由于题目没有强制在线，先考虑离线。

我们发现凸包删点事件非常麻烦的事情，考虑将一直没删的点建立凸包后再倒序加点，这时如果存在同时增删点则做线段树分治。

加点时先考虑所加点是否在凸包外，在凸包里面的不加入。另外加入是注意两边都要判断，如果出现左拐则删除，保证凸包涉及的边按顺时针（从左到右）顺序斜率单减。注意比较时用浮点数不好，建议交叉相乘。

维护时考虑用 stl :: set，这样我们会有总体

\operatorname{O}(m\log m)

的动态加点操作，于是题目解决了。

代码

CPP

//c++14 O2,213ms,3.59mb,2.52kb
#include<bits/stdc++.h>
using namespace std;
int n,m,q,tp[200009],id[200009],x,y,a[100009],b[100009];
bool vis[200009];
set<pair<int,int> >p;
double ans,prt[200009];
double dis(int x1,int y1,int x2,int y2){
	return __builtin_sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
void delnode(set<pair<int,int> > :: iterator x){
	auto y = x,z = x;
	//printf("d %d %d\n",x -> first,x -> second);
	y ++,z --;
	ans -= dis(y -> first,y -> second,x -> first,x -> second);
	ans -= dis(z -> first,z -> second,x -> first,x -> second);
	ans += dis(y -> first,y -> second,z -> first,z -> second);
	p.erase(x);
//	printf("%.2lf\n",ans);
}
void addnode(int x,int y){
	//printf("a %d %d\n",x,y);
	auto fx = p.insert(make_pair(x,y)).first;
	auto fy = fx,z = fx;
	fy ++,z --;
	//printf("%d %d %d %d\n",fy -> first,fy -> second,z -> first,z -> second);
	ans += dis(fy -> first,fy -> second,fx -> first,fx -> second);
	ans += dis(z -> first,z -> second,fx -> first,fx -> second);
	ans -= dis(fy -> first,fy -> second,z -> first,z -> second);
}
void pop(int x,int y){
	auto o = p.lower_bound(make_pair(x,y)),fp = o;
	if(o == p.end())
		return;
	fp ++;
	while(p.end() != fp && (o -> second - y) * (fp -> first - o -> first) <= (o -> first - x) * (fp -> second - o -> second))
		delnode(o),o = fp,fp ++;
	o --;
	fp = o;
	if(o == p.begin())
		return;
		fp --;
	while((y - o -> second) * (o -> first - fp -> first) >= (x - o -> first) * (o -> second - fp -> second)){
		delnode(o);
		o = fp;
		if(o != p.begin())
			fp --;
		else
			break;
	}
}
void ins(int x,int y){
	auto o = p.lower_bound(make_pair(x,y));
	auto fp = o;
	fp --;
	if(o -> first == x)
		return;
	else if(fp -> first == x){
		delnode(fp);
		pop(x,y);
		addnode(x,y);
	}
	else if((o -> second - y) * (x - fp -> first) < (o -> first - x) * (y - fp -> second))
		pop(x,y),addnode(x,y);
}
/*
Author:OtterZ
Tag:offline,slope trick,geometry
*/
int main(){
	scanf("%d %d %d",&n,&x,&y);
	ans = __builtin_sqrt(x * x + y * y) + __builtin_sqrt((n - x) * (n - x) + y * y);
	p.insert(make_pair(0,0)),p.insert(make_pair(n,0)),p.insert(make_pair(x,y));
	scanf("%d",&m);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&a[i],&b[i]);
	}
	scanf("%d",&q);
	for(int i = 1; i <= q; i ++){
		scanf("%d",&tp[i]);
		if(tp[i] == 1){
			scanf("%d",&id[i]);
			if(vis[id[i]])
				id[i] = 0;
			vis[id[i]] = true;
		}
	}
	for(int i = 1; i <= m; i ++)
		if(!vis[i])
			ins(a[i],b[i]);
	for(int i = q; i > 0; i --){
		if(id[i] != 0)
			ins(a[id[i]],b[id[i]]);
		else if(tp[i] == 2)
			prt[i] = ans;
		//printf("%.2lf\n",ans);
	}
	for(int i = 1; i <= q; i ++)
		if(tp[i] == 2)
			printf("%.2lf\n",prt[i]);
	return 0;
}

题解：P2521 [HAOI2011] 防线修建

文章操作

题意

解法

代码

相关推荐

评论

题解：P2521 [HAOI2011] 防线修建