十一选五玩法及奖金:BZOJ 1007, 水平可见直线

吉林省十一选五走势图 www.el2sw.cn 2017-2-10来源:ASP.NET技巧人气:4659

PRoblem

传送门

Mean

参见题目描述。

Analysis

将直线按斜率排序,然后从小到大依次入栈,入栈时计算该直线与栈顶元素交点。 若该交点在栈顶元素与栈顶下一个元素交点的左侧(或重合),则栈顶元素被完整遮挡,出栈。 反复比较,全部操作完毕后栈中元素即为可见水平直线。

Code

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double EPS=1e-10; const int N=50005; int n,top,s[N]; bool f[N]; struct Line{ int id; double a,b; bool Operator < (const Line &B) const { if(fabs(a-B.a)<EPS) return b<B.b; return a<B.a; } }l[N]; double Cross(Line A,Line B){return (B.b-A.b)/(A.a-B.a);} int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&l[i].a,&l[i].b); l[i].id=i; } sort(l,l+n); for(int i=0;i<n;i++){ while(top){ if(fabs(l[s[top]].a-l[i].a)<EPS) top--; else if(top>1 && Cross(l[s[top]],l[i])<=Cross(l[s[top-1]],l[s[top]])) top--; else break; } s[++top]=i; } for(int i=1;i<=top;i++) f[l[s[i]].id]=1; for(int i=0;i<n;i++) if(f[i]) printf("%d ",i+1); return 0; }

  • 紫光阁中共中央国家机关工作委员会 2018-12-16
  • 反思顾雏军案,营造可预期的法治环境 2018-12-16
  • 用餐遇收取包厢费、开瓶费、餐具消毒费等请举报 2018-12-15
  • 阿根廷纸糊后防!半场没丢3个算命大 光靠梅西有啥用 2018-12-14
  • 山西:今年汛期降雨量偏多 各部门未雨绸缪全力备汛 2018-12-13
  • 多家媒体聚焦国防邮电行业工匠 2018-12-12
  • 回复@看着就想笑:真有点赞机,还不点个百八十个赞 2018-12-12
  • 十九大精神宣讲团报道集 2018-12-11
  • 上海市8名市管干部提任前公示 2018-12-10
  • 打造金融科技交流平台 中小银行互联网金融(深圳)联盟成立 2018-12-09
  • 浦东新区:探索人民调解专业化 2018-12-08
  • 辽宁:电商成为精准扶贫的“利器” 2018-12-07
  • 长江中下游正式“入梅”!中东部高温降雨齐上阵 湖北中北部有大到暴雨 2018-12-07
  • 中央纪委通报88起侵害群众利益的不正之风和腐败问题 2018-12-06
  • 爱这个世界——“凤凰好书榜6月榜”发布 2018-12-05
  • 138| 186| 701| 368| 829| 540| 386| 362| 57| 640|