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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1007]水平可见直线  

2014-05-07 17:39:49|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
初中数学+单调栈
感觉暴力维护会T
百度看到了"单调栈"
然后就会了
按照斜率排个序,然后该弹的时候弹一下,时间复杂度O(n)
初中数学渣爆求拯救

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
const int N = 50000+1;
struct line{
int a,b,x;
line(){}
line(int aa,int bb):a(aa),b(bb){}
}lines[N];
struct Point{
int x, y;
Point (){}
Point (int xx,int yy):x(xx),y(yy){}
};
bool operator == (line a,line b){return (a.a==b.a&&a.b==b.b);}
struct Stack{
int top;
line d[N];
}stack;
int n,m,ans[N];
bool cmp(line a,line b){
if(a.a!=b.a)return a.a<b.a;
else return a.b<b.b;
}
const double eps = 1e-10;
bool pcmp(line a,line b,line c){
double x1,x2;
x1=(double)(c.b-a.b)/(a.a-c.a);
x2=(double)(b.b-a.b)/(a.a-b.a);
return (x1<x2)||fabs(x1-x2)<=eps;
}
int main(){
int i,j,a,b;
n=scan();
for(i=1;i<=n;i++){
a=scan();b=scan();
lines[i]=line(a,b);
lines[i].x=i;
}
sort(lines+1,lines+1+n,cmp);
n=unique(lines+1,lines+1+n)-lines-1;
for(i=1;i<=n;i++){
line now=lines[i];
//pop it
while(stack.top > 0&&lines[stack.top].a==now.a)stack.top--;
while(stack.top > 1&&pcmp(stack.d[stack.top-1],stack.d[stack.top],now)) stack.top--;
stack.d[++stack.top]=now;
/*
for(j=1;j<=stack.top;j++)
printf("%d ",stack.d[j].x);
printf("\n");*/
}
for(i=1;i<=stack.top;i++)
ans[i]=stack.d[i].x;
sort(ans+1,ans+1+stack.top);
for(i=1;i<=stack.top;i++)
printf("%d ",ans[i]);
printf("\n");
return 0;
}


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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