cogs 547:[HAOI2011] 防线修建
★★★☆ 输入文件:defense.in
输出文件:defense.out
简单对比
时间限制:1 s 内存限制:128 MB
题目描述:
近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务:
给出你所有的A国城市坐标
A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了
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以内, 数据保证没有重点
题解:
此题要求动态地去维护一个凸包的周长,我们可以发现,要想从凸包上删除一个点然后更新答案并不容易,因为凸包内部的点的信息不好维护,不妨把所有操作先存下来,离线反向操作。每碰到一个操作1,添加一个点,添加点无非是看这个点是在凸包的内部还是外部,内部的就不用管了,对答案并没有什么卵用,如果是在外部,就看在这个点左边的凸包上的点和右边凸包上的点会不会被覆盖,这个用向量的叉积判断即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
const double eps=1e-;
int n,x,y,m,q;
double now;
struct Q{
int kin,i;
double ans;
}opt[];
bool vis[];
struct P{
int x,y;
}p[],del[];
inline P operator-(P a,P b){
P t; t.x=a.x-b.x; t.y=a.y-b.y;
return t;
}
inline double operator*(P a,P b){
return a.x*b.y-b.x*a.y;
}
inline bool operator<(P a,P b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
inline double dis(P a,P b){
return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
} set<P> A;
inline void insert(int a,int b){
P x=(P){a,b};
set<P>::iterator r=A.lower_bound(x),l=r,t;
l--;
if((*l-x)*(*r-x)<) return ;
now-=dis(*l,*r);
A.insert(x);
while(r!=A.end()){
t=r; r++;
if((*r-x)*(*t-x)>) break;
now-=dis(*t,*r);
A.erase(t);
}
while(l!=A.begin()){
t=l; l--;
if((*t-x)*(*l-x)>) break;
now-=dis(*t,*l);
A.erase(t);
}
A.insert(x);
l=r=t=A.find(x);
l--; r++;
now+=dis(*l,x)+dis(*r,x);
} int main(){
// freopen("defense.in","r",stdin);
// freopen("defense.out","w",stdout);
scanf("%d%d%d",&n,&x,&y);
scanf("%d",&m);
for(int i=;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y);
scanf("%d",&q);
for(int i=;i<=q;i++){
scanf("%d",&opt[i].kin);
if(opt[i].kin==){
scanf("%d",&opt[i].i);
vis[opt[i].i]=true;
}
}
P cap; cap.x=x; cap.y=y;
now+=dis((P){,},cap); now+=dis((P){n,},cap);
A.insert((P){,}); A.insert((P){n,}); A.insert((P){x,y});
for(int i=;i<=m;i++){
if(vis[i]==false) insert(p[i].x,p[i].y);
}
for(int i=q;i>=;i--){
if(opt[i].kin==){
opt[i].ans=now;
}
else{
insert(p[opt[i].i].x,p[opt[i].i].y);
}
}
for(int i=;i<=q;i++){
if(opt[i].kin==){
printf("%.2lf\n",opt[i].ans);
}
}
return ;
}
最新文章
- lamp 环境搭建
- Fragment的生命周期(三)
- 骑士cms(74cms)个人版 整合UC
- 用sql的select语句从数据库中获取数据
- 练习题之Wait/Notify
- hdu 5640 King&#39;s Cake(模拟)
- 2048 Puzzle游戏攻略
- 1.3. 创建 Grocery Dude 项目(Core Data 应用程序实践指南)
- Hadoop学习笔记-001-CentOS_6.5_64_连接外网设置
- 枚举类TimeUnit
- ajax错误处理 500错误
- GDAL C#中文路径,中文属性名称乱码问题
- Effective Java 第三版——39. 注解优于命名模式
- eclipse下解决明明有jar包,却找不到的问题
- CENTOS 7 安装 TINYPROXY 代理服务器
- 数组中array==null和array.length==0的区别
- winfrom中pictureBox控件的部分使用方法
- smarty半小时快速上手教程
- MVC5 Api Area 区域
- SpringMVC中fastjson支持jsonp的实现