bzoj1007[HNOI2008]水平可見直線

題意：

平面上有n條直線L1,L2,...Ln,若在y值為正無窮大處往下看,能見到Li的某個子線段,則稱Li為可見的,否則Li為被覆蓋的。給出n條直線,已知其斜率和截距,且n條直線兩兩不重合，求出所有可見的直線。

題解：

和上一道差不多，但是因為是比較隨意的直線，所以還要多一些判斷條件。

代碼：

1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define eps 1e-8 7 using namespace std; 8 9 struct nd{ 10 int a,b,id; 11 bool operator < (const nd& x)const{ 12 if(a!=x.a)return a<x.a; return b<x.b; 13 } 14 }; 15 double solve(nd a,nd b){ 16 return (double)(a.b-b.b)/(double)(b.a-a.a); 17 } 18 nd nds[100000],s[100000]; int ans[100000],n,tp; 19 int main(){ 20 scanf("%d",&n);inc(i,1,n)scanf("%d",&nds[i].a),scanf("%d",&nds[i].b),nds[i].id=i; sort(nds+1,nds+1+n); 21 tp=1;s[tp]=nds[1];ans[tp]=nds[1].id; 22 inc(i,2,n){ 23 if(nds[i].a-s[tp].a==0)tp--; 24 while(tp>=2&&solve(s[tp-1],s[tp])>=solve(s[tp],nds[i]))tp--; 25 s[++tp]=nds[i]; ans[tp]=nds[i].id; 26 } 27 sort(ans+1,ans+1+tp);inc(i,1,tp)printf("%d ",ans[i]); 28 return 0; 29 }

?

20160407

轉載于:https://www.cnblogs.com/YuanZiming/p/5696932.html

總結

以上是生活随笔為你收集整理的bzoj1007[HNOI2008]水平可见直线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。