HAOI2011 防线修建（动态凸包）

发表于 |
字数统计: 1,327字 | 阅读时长 ≈ 7min

【HAOI2011 Day1】防线修建

问题描述

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

上图中，A,B,C,D,E点为A国城市，且目前都要保护，那么修建的防线就会是A-B-C-D，花费也就是线段AB的长度+线段BC的长度+线段CD的长度

如果，这个时候撤销B点的保护，那么防线变成下图

输入格式

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

第二行，一个整数m。

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

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

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

输出格式

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

样例输入

4 2 1

2

1 2

3 2

5

2

1 1

2

1 2

2

样例输出

6.47

5.84

4.47

数据范围：

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

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

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

动态凸包裸题，用set维护一下就好了，每次就查找前后的点判断一下凸性质，不满足就弹掉。

代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<cmath>
#define N 100005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct node{int x,y;}P[N],Q[N];
int n,X,Y,m,q;
bool use[N];
set<node>S;
double ans,Ans[N];
bool operator<(node a,node b)
{
	if(a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
int operator*(node a,node b){return a.x*b.y-a.y*b.x;}
double dis(node a,node b)
{
	double x=a.x-b.x;
	double y=a.y-b.y;
	return sqrt(x*x+y*y);
}
bool judge(node a,node b,node c)
{
	return (c-b)*(a-b)>=0;
}
set<node>::iterator Gpre(node p)
{
	set<node>::iterator it=S.lower_bound(p);
	if(it!=S.begin())return --it;
	return it;
}
set<node>::iterator Gsuc(node p)
{
	set<node>::iterator it=S.upper_bound(p);
	if(it!=S.end())return it;
	return --it;
}
bool PopF(node p)
{
	set<node>::iterator p1=Gpre(p);
	set<node>::iterator p2=Gpre(*p1);
	if(p1==p2)return 0;
	if(judge(*p2,*p1,p))
	{
		ans-=dis(*p2,*p1);
		ans-=dis(*p1,p);
		ans+=dis(*p2,p);
		S.erase(p1);return 1;
	}
	return 0;
}
bool PopB(node p)
{
	set<node>::iterator p1=Gsuc(p);
	set<node>::iterator p2=Gsuc(*p1);
	if(p1==p2)return 0;
	if(judge(p,*p1,*p2))
	{
		ans-=dis(*p1,*p2);
		ans-=dis(p,*p1);
		ans+=dis(p,*p2);
		S.erase(p1);return 1;
	}
	return 0;
}
void Ins(node p)
{
	set<node>::iterator suc=Gsuc(p);
	set<node>::iterator pre=Gpre(p);
	if(judge(*pre,p,*suc))return;
	S.insert(p);ans-=dis(*pre,*suc);
	ans+=dis(*pre,p)+dis(p,*suc);
	while(PopF(p));while(PopB(p));
}
int main()
{
	int i,j,k,x,y;
	_R(n);_R(X);_R(Y);_R(m);
	for(i=1;i<=m;i++)_R(P[i].x),_R(P[i].y);
	_R(q);
	for(i=1;i<=q;i++)
	{
		_R(k);
		if(k==2)Q[i]=(node){2,0};
		else
		{
			_R(x);use[x]=1;
			Q[i]=(node){1,x};
		}
	}
	S.insert((node){0,0});
	S.insert((node){n,0});
	S.insert((node){X,Y});
	ans=dis((node){0,0},(node){X,Y})+dis((node){X,Y},(node){n,0});
	for(i=1;i<=m;i++)if(!use[i])Ins(P[i]);
	for(i=q;i>=1;i--)
	{
		if(Q[i].x==2)Ans[i]=ans;
		else Ins(P[Q[i].y]);
	}
	for(i=1;i<=q;i++)if(Q[i].x==2)printf("%.2lf\n",Ans[i]);
}