LA 4253 箭术（二分枚举）

https://vjudge.net/problem/UVALive-4253

题意：

有n个平行于x轴的线段，每条线段代表一个靶子。判断是否可以站在x轴上[0,W]区间内的某个位置射箭。

思路：
二分枚举坐标点，这道题需要用到atan2函数，它返回一个角度值，对于每个靶子，利用atan2函数确定能射中靶子的区间，如果靶子之间区间没有重合部分，说明该坐标点不能射中所有靶子。在下面的代码中，如果返回1，说明需要向右移，如果返回-1，说明需要向左移。

这道题目还需要注意一点的就是精度问题。

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn =  + ;

 double W;

 int n;

 struct node

 {

     double D, L, R;

 }a[maxn];

 bool cmp(node a, node b)

 {

     return a.D < b.D;

 }

 int judge(double pos)

 {

     double R = atan2(a[].D, a[].R - pos);

     double L = atan2(a[].D, a[].L - pos);

     for (int i = ; i < n; i++)

     {

         double r = atan2(a[i].D, a[i].R - pos);

         double l = atan2(a[i].D, a[i].L - pos);

         if (l - R < -0.000001)    return -;

         if (r - L > 0.000001)    return ;

         L = min(L, l);

         R = max(R, r);

     }

     return ;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int T;

     cin >> T;

     while (T--)

     {

         cin >> W >> n;

         for (int i = ; i < n; i++)

             cin >> a[i].D >> a[i].L >> a[i].R;

         sort(a, a + n, cmp);

         double l = , r = W;

         int ok = ;

         while (r - l>0.0000001)

         {

             double mid = (r + l) / ;

             int ans = judge(mid);

             if (ans == )

             {

                 cout << "YES" << endl;

                 ok = ;

                 break;

             }

             else if (ans == )  l = mid;

             else  r = mid;

         }

         if(!ok) cout << "NO" << endl;

     }

 }