LA 4253 箭术（二分枚举）

题意：

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

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

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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 const int maxn = 5000 + 5;
 8 
 9 double W;
10 int n;
11 
12 struct node
13 {
14     double D, L, R;
15 }a[maxn];
16 
17 bool cmp(node a, node b)
18 {
19     return a.D < b.D;
20 }
21 
22 int judge(double pos)
23 {
24     double R = atan2(a[0].D, a[0].R - pos);
25     double L = atan2(a[0].D, a[0].L - pos);
26     for (int i = 1; i < n; i++)
27     {
28         double r = atan2(a[i].D, a[i].R - pos);
29         double l = atan2(a[i].D, a[i].L - pos);
30 
31         if (l - R < -0.000001)    return -1;
32         if (r - L > 0.000001)    return 1;
33 
34         L = min(L, l);
35         R = max(R, r);
36     }
37     return 0;
38 }
39 
40 
41 int main()
42 {
43     //freopen("D:\txt.txt", "r", stdin);
44     int T;
45     cin >> T;
46     while (T--)
47     {
48         cin >> W >> n;
49         for (int i = 0; i < n; i++)
50             cin >> a[i].D >> a[i].L >> a[i].R;
51         sort(a, a + n, cmp);
52         double l = 0, r = W;
53         int ok = 0;
54         while (r - l>0.0000001)
55         {
56             double mid = (r + l) / 2;
57             int ans = judge(mid);
58             if (ans == 0)
59             {
60                 cout << "YES" << endl;
61                 ok = 1;
62                 break;
63             }
64             else if (ans == 1)  l = mid;
65             else  r = mid;
66         }
67         if(!ok) cout << "NO" << endl;
68     }
69 }