bzoj [Usaco2009 Hol]Cattle Bruisers 殺手游戲

Description

Input

?第1行輸入N，R，BX，BY,?BVX，BVY，之后N行每行輸入四個整數Xi，Yi，VXi，VYi．

Output

????一個整數，表示在逃脫過程中，某一個時刻最多有這個數理的殺手可以射殺貝茜．

Sample Input

3 1 0 0 0 2
0 -3 0 4
1 2 -1 1
1 -2 2 -1

Sample Output

2

OUTPUT DETAILS:

At time 1.5, Bessie is at point (0, 3), and the three bruisers are
at points (0, 3), (-0.5, 3.5), and (4, -3.5). The first two cattle
bruisers are within 1 unit of Bessie, while the third will never
be within 1 unit of Bessie, so 2 is the most achievable.

思路:? 我們可以計算出每個殺手可以射擊的一個時間范圍，然后做掃描線。時間復雜度$O(nlogn)$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int const N = 50000 + 3;
 4 double const eps = 1e-8;
 5 int n, r, m, in[N], out[N], cnt;
 6 double bx, by, bvx, bvy, x[N], y[N], vx[N], vy[N], t1[N], t2[N], t[N << 2];
 7 void calc(int k) {
 8     double tx = x[k] - bx;
 9     double ty = y[k] - by;
10     double v1 = vx[k] - bvx;
11     double v2 = vy[k] - bvy;
12     double a = v1 * v1 + v2 * v2;
13     double b = 2 * v1 * tx + 2 * v2 * ty;
14     double c = tx * tx + ty * ty - 1.0*r * r;
15     double d = b * b - 4 * a * c;
16     if(fabs(a) < eps ) {
17         if( c<0) { // 這個我始終覺得很奇怪，為什么c小于0就無限解了。
18             m++;
19             t1[m] = 0;
20             t2[m] = 1e10;
21         }
22         return ;
23     }
24     if(d<0) return ;
25     t1[k] = (-b - sqrt(d)) / (2 * a);
26     t2[k] = (-b + sqrt(d)) / (2 * a);
27     if(t2[k] <0)
28         return ;
29     t1[k] = max(0.0, t1[k]);
30     m++;
31     t1[m] = t1[k];
32     t2[m] = t2[k];
33 }
34 int main() {
35     scanf("%d%d%lf%lf%lf%lf", &n, &r, &bx, &by, &bvx, &bvy);
36     for(int i = 1; i <= n; i++) {
37         scanf("%lf%lf%lf%lf", &x[i], &y[i], &vx[i], &vy[i]);
38         calc(i);
39     }
40     for(int i = 1; i <= m; i++) {
41         ++cnt;
42         t[cnt] = t1[i];
43         ++cnt;
44         t[cnt] = t2[i];
45     }
46     sort(t + 1, t + cnt + 1);
47     int c = unique(t, t + cnt + 1) - t - 1;
48     for(int i = 1; i <= m; i++) {
49         int a = lower_bound(t + 1, t + c + 1, t1[i]) - t;
50         int b = lower_bound(t + 1, t + c + 1, t2[i]) - t;
51         in[a]++;
52         out[b]++;
53     }
54     int ans = 0, now = 0;
55     for(int i = 1; i <= c; i++) {
56         now += in[i];
57         ans = max(ans, now);
58         now -= out[i];
59     }
60     printf("%d\n", ans);
61     return 0;
62 }

View Code

轉載于:https://www.cnblogs.com/ZJXXCN/p/10771266.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/249063.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/249063.shtml
英文地址，請注明出處：http://en.pswp.cn/news/249063.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！