麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

BZOJ 1007, 水平可見(jiàn)直線

2019-11-11 05:07:37
字體：大 中 小
來(lái)源：轉(zhuǎn)載
供稿：網(wǎng)友

PRoblem

傳送門

Mean

參見(jiàn)題目描述。

Analysis

將直線按斜率排序，然后從小到大依次入棧，入棧時(shí)計(jì)算該直線與棧頂元素交點(diǎn)。 若該交點(diǎn)在棧頂元素與棧頂下一個(gè)元素交點(diǎn)的左側(cè)（或重合），則棧頂元素被完整遮擋，出棧。 反復(fù)比較，全部操作完畢后棧中元素即為可見(jiàn)水平直線。

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;}

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板： 成人午夜在线免费观看 | 噜噜噜躁狠狠躁狠狠精品视频 | 国产色视频一区 | 久久99精品久久久久久园产越南 | 毛片在线免费 | 美国人成人在线视频 | 久久久久久久亚洲精品 | 毛片免费看的 | 国产正在播放 | 日韩黄色av网站 | 成人在线免费观看小视频 | 18一20岁一级毛片 | 久久久久久久久国产 | 鲁久久| 亚洲第五色综合网 | 成人mm视频在线观看 | 一级一级一级毛片 | 欧美日韩a∨毛片一区 | 线观看免费完整aaa 欧美在线一级 | 高清国产午夜精品久久久久久 | 最新久久免费视频 | 国产精品成人一区二区三区吃奶 | 性欧美xxxx极品摘花 | aa级黄色片 | 欧美不卡三区 | free性欧美hd另类 | 国产一级免费电影 | 日韩精品一区二 | 狠狠干b | 久久精品国产精品亚洲 | 欧美爱爱视频 | 羞羞的网站 | 免费一级欧美大片视频 | 国产精品午夜在线观看 | 黄网站色成年大片免费高 | 国产成人午夜精品 | 成年人黄色免费网站 | 性爱视频在线免费 | 国产妇女乱码一区二区三区 | 日本不卡一区二区三区在线 | 国产精品免费成人 |