题意:有n个平行于x轴的线段，每条线段代表一个靶子，你的任务是判断是否可以站在x轴上[0,w]区间的某个位置射箭使其射到所有靶子，箭沿直线飞行且一定会射穿每一个靶子。注意箭可以在某一个位置朝任何方向发射
如果存在这样一个点，输出YES,否则输出NO
这题还是很有思维训练难度的，要用到二分
二分枚举每一个射箭点，然后依次计算箭射到每一个靶子上的角度区间，如果有任何一对靶子的区间没有交集就说明不能有，否则就可以有
这里又学到了一个新函数:atan2(y,x),即计算tan值为y/x的角度
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; const double jd=1e-4; double w; int n; struct wk{double y,xl,xr;}s[5005]; bool cmp(wk a,wk b){return a.y<b.y;} int check(double k){ double L=atan2(s[1].y,s[1].xr-k); double R=atan2(s[1].y,s[1].xl-k); for(int i=2;i<=n;i++){ double l=atan2(s[i].y,s[i].xr-k); double r=atan2(s[i].y,s[i].xl-k); if(L-r>jd)return -1; if(l-R>jd)return 1; R=min(r,R); L=max(L,l); } return 0; } int main(){ int i,j,t; scanf("%d",&t); while(t--){ scanf("%lf%d",&w,&n); for(i=1;i<=n;i++) scanf("%lf%lf%lf",&s[i].y,&s[i].xl,&s[i].xr); sort(s+1,s+1+n,cmp); double l=0,r=w,mid; bool mark=1; while(r-l>jd&&mark){ mid=(l+r)/2; int flag=check(mid); if(flag==1)l=mid; if(flag==-1)r=mid; if(flag==0)mark=0; } if(mark)puts("NO"); else puts("YES"); } }
