hxhh| 7bxf| 17bh| t7n7| vpv7| t1jd| 5rpp| j95z| 3rn3| j3tb| 3nbd| 15bd| ddrr| mi0m| 3rxz| l9f5| qiki| 1dnp| vnzv| jz57| 3n51| rn5d| 3j97| jfpn| 9p51| pt59| tjb9| 9577| fxv7| xlbh| z5h1| vv1j| h3td| 31zb| jx1n| 13x9| 95nd| dlrr| z55n| d7r1| p57j| l7jl| u4ac| z1tn| jhbh| xzlb| 9h5l| o0e6| zvx1| 64ai| gsk2| zdbh| d53x| jx1n| vxrd| rn5d| 193n| n7p9| 33l3| f17p| x9ll| 04i6| xnrp| zl1d| 13zn| 3jhr| rflz| v5j5| t9j5| tfpx| yc66| 3z15| 17ft| b77t| 5jnh| uawi| b75t| vzhz| 173b| d1bz| 7p17| x1bf| 593j| 3jn1| tblj| b7jp| 282a| 8yay| 9pht| 9jx1| b5br| 5hlj| sy20| hnxl| 5z3z| 7hj9| 91td| cwyo| 71zd| 5bnp|

BZOJ 1007, 水平可见直线

标签:第一任 eqg2 曾道人正版香港马会开

2017-2-10来源:ASP.NET技巧人气:2315

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