列出不等式，二分，半平面交判定。注意可行域可能為點或線段或無界區(qū)域。坐標范圍略大，算出來a的范圍約為-1e9~-1e-18（a<0），理論上要用long double，不過好像double也能過。

#include<algorithm> #include<cstdio> #include<cmath> using std::sort; typedef long double flo; const flo eps=1e-24; const int N=2e5+5; int m; struct vec{flo x,y;}; flo det(vec a,vec b){return a.x*b.y-a.y*b.x;} vec operator+(vec a,vec b){return(vec){a.x+b.x,a.y+b.y};} vec operator-(vec a,vec b){return(vec){a.x-b.x,a.y-b.y};} vec operator*(flo a,vec b){return(vec){a*b.x,a*b.y};} struct line{int i;vec p,v;flo a;void cal(){a=atan2(v.y,v.x);} }c[N],q[N]; flo cal(vec a,line b){return det(a-b.p,b.v);} bool operator<(line a,line b){return a.a<b.a||a.a==b.a&&cal(a.p,b)<0; } vec over(line a,line b){return a.p+det(a.p-b.p,b.v)/det(b.v,a.v)*a.v; } bool jud(int s){int a=0,b=-1;for(int i=0;i<m;++i)if(c[i].i<=s)if(a>b||fabs(c[i].a-q[b].a)>eps){while(a<b&&cal(over(q[b],q[b-1]),c[i])>0)--b;while(a<b&&cal(over(q[a],q[a+1]),c[i])>0)++a;q[++b]=c[i];}while(a<b&&cal(over(q[b],q[b-1]),q[a])>0)--b;return b-a>1; } int main(){struct{operator int(){int x=0,c=getchar();while(c<48)c=getchar();while(c>47)x=x*10+c-48,c=getchar();return x;}}it;c[m++]=(line){0,-1e9,0,0,-1};c[m++]=(line){0,-1e-18,0,0,1};int n=it;for(int i=1;i<=n;++i){flo x=it,y1=it,y2=it;c[m++]=(line){i,0,y1/x,1,-x};c[m++]=(line){i,0,y2/x,-1,x};}for(int i=0;i<m;++i)c[i].cal();sort(c,c+m);int l=1,r=n;while(l!=r){int j=l+r+1>>1;jud(j)?l=j:r=j-1;}printf("%d\n",l); }

轉(zhuǎn)載于:https://www.cnblogs.com/f321dd/p/5538318.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ2732: [HNOI2012]射箭的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。