注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2300][HAOI2011]防线修建  

2014-12-17 21:39:09|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2300: [HAOI2011]防线修建

才发现今天刷的三道题居然题号是连着的
我明明是随便挑题做的……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1E5+100;
typedef long long ll;
typedef pair<int,int> Point;
int n,m,ask[N*2],end;
short del[N];
double ans,out[N];
Point data[N],sdat[N],ke[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
double dis(const Point &a,const Point &b){
double re=0;
re = hypot(a.first-b.first,a.second-b.second);
return re;
}
bool cmp (const Point &a,const Point &b){return a.first==b.first?a.second>b.second:a.first<b.first;}
bool operator < (Point &a,Point &b){return a.first<b.first;}
int cross(Point a,Point b){return a.first*b.second - a.second*b.first;}
Point operator - (const Point &a,const Point &b){return Point(a.first-b.first,a.second-b.second);}
set<Point>tk;
typedef set<Point>::iterator Node;
void print(Point a){
printf("%d %d\n",a.first,a.second);
}
void add(const Point &ins,short type=0){
Node now,tmp[2];
if(!type){
tmp[1] = tk.lower_bound(ins);
tmp[0] = tmp[1];
tmp[0]--;
if(cross(*tmp[0]-ins,ins-*tmp[1])>=0)return;
tk.insert(ins);
}
now = tk.lower_bound(ins);

tmp[0] = now;tmp[0]--;
tmp[1] = now;tmp[1]++;
if(!type){
ans -= dis(*tmp[0],*tmp[1]);
}else{
/*
print(*now);
print(*tmp[0]);
print(*tmp[1]);*/
ans -= dis(*tmp[0],*now) + dis(*tmp[1],*now);
//printf("<%.2f>",ans);
tk.erase(now);
tk.insert(ins);
now = tk.lower_bound(ins);
tmp[0] = now;tmp[0]--;
}
//pre
while(tmp[0]->first>0){
tmp[1] = tmp[0];tmp[1]--;
if(cross(*tmp[1]-*tmp[0],*tmp[0]-*now)<0)break;
ans -= dis(*tmp[0],*tmp[1]);
tk.erase(tmp[0]);
now = tk.lower_bound(ins);
tmp[0] = now;tmp[0]--;
}
ans += dis(*tmp[0],*now);

tmp[0] = now;tmp[0]++;
while(tmp[0]->first<end){
tmp[1] = tmp[0];tmp[1]++;
if(cross(*now-*tmp[0],*tmp[0]-*tmp[1])<0)break;
ans -= dis(*tmp[0],*tmp[1]);
tk.erase(tmp[0]);
now = tk.lower_bound(ins);
tmp[0] = now;tmp[0]++;
}
ans += dis(*tmp[0],*now);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
end = scan();
data[++n] = Point(0,0);
data[++n] = Point(end,0);
a = scan();b = scan();
data[++n] = Point(a,b);
m = scan();
for(i=1;i<=m;i++){
a = scan();b = scan();
data[++n] = Point(a,b);
}
m = scan();
for(i=1;i<=m;i++){
a = scan();
if(a==1){
ask[i] = scan()+3;
del[ask[i]]=1;
}else ask[i]=-1;
}
for(i=1;i<=n;i++)
if(!del[i])sdat[i] = data[i];
else sdat[i]=data[1];
sort(sdat+1,sdat+1+n,cmp);

int kn=0;
ke[++kn] = sdat[1];
for(i=2;i<=n;i++)
if(sdat[i].first != sdat[i-1].first){
while(kn > 1 && cross(ke[kn-1]-ke[kn],ke[kn]-sdat[i])>=0)kn--;
ke[++kn] = sdat[i];
}
for(i=1;i<=kn;i++){
tk.insert(ke[i]);
//printf("%d %d\n",ke[i].first,ke[i].second);
if(i>1)ans += dis(ke[i-1],ke[i]);
}
//for(i=1;i<=m;i++)printf("%d ",ask[i]);printf("\n");
for(i=m;i;i--)
if(ask[i]>0){
//printf("[%d]\n",i);
//printf("%d\n",tk.count(data[ask[i]]));
Node tmp = tk.find(data[ask[i]]);
//if(tmp==tk.end())printf("ahhas");
//print(*tmp);
if(tmp!=tk.end()){
if(tmp->second<data[ask[i]].second)
add(data[ask[i]],1);
}else
add(data[ask[i]]);
}else if(ask[i]<0){
out[i] = ans;
}
for(i=1;i<=m;i++)
if(ask[i]<0)printf("%.2f\n",out[i]);
return 0;
}

题解:
平衡树动态维护凸壳
偷懒用了set……下次一定自己好好手写splay
没想到还挺快,在第二页
应该是因为数据水+BZOJ上有氧气(O2)  生成了氢气燃烧后加速了代码运行速度(雾
一开始因为没讨论加进去的点是否有意义WA了一次……
  评论这张
 
阅读(141)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017