METEOR (DHBB 2021 T.Thử)

Xem PDF




Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Các nhà khoa học của NASA luôn theo dõi những thiên thạch có tiềm năng tiếp cận Trái Đất. So với vũ trụ rộng lớn,
các thiên thạch và Trái Đất đều có thể coi là một điểm. Để đơn giản, Trái Đất được coi là gốc của hệ trục toạ độ
Oxyz. Các nhà khoa học đang theo dõi \(n\) thiên thạch. Tại thời điểm 0, thiên thạch thứ \(i\) đang ở điểm (\(x_i, y_i, z_i\)) và di chuyển với vận tốc (\(vx_i, vy_i, vz_i\)). Một thiên thạch được coi là nguy hiểm nếu khoảng cách từ nó đến Trái Đất không
vượt quá \(R\). Các nhà khoa học xác định được \(m\) thời điểm quan trọng. Họ cần xác định xem tại mỗi thời điểm quan
trọng, có bao nhiêu thiên thạch nguy hiểm.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(R\). (\(1 \le n \le 100000; 1 \le R \le 1000000\)).
  • \(n\) dòng sau, mỗi dòng chứa sáu số nguyên \(x, y, z, vx, vy\)\(vz\) (\(|x|, |y|, |z| \le 1000000; |vx|, |vy|, |vz| \le 100\)) cho biết vị trí tại thời điểm 0 và vận tốc của
    một thiên thạch.
  • Dòng tiếp theo chứa số nguyên \(m\) (\(1 \le m \le 100000\)).
  • Sau đó là \(m\) dòng, mỗi dòng chứa một số
    nguyên \(t\) (\(0 \le t \le 10000000\)) là một thời điểm quan trọng.

Output

  • Với mỗi thời điểm quan trọng, ghi ra trên một dòng một số nguyên duy nhất là số lượng thiên thạch nguy hiểm.

Example

Test 1

Input
1 1 
-2 0 0 1 0 0 
5 
0 
1 
2 
3 
4 
Output
0 
1 
1 
1 
0

Bình luận


  • 0
    htrung1105 4:40 p.m. 7 Tháng 5, 2021

    Mọi người giúp em với, em cứ bị TLE test 3:
    Code:

    pragma gcc optimize 02

    include<bits/stdc++.h>

    define FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    using namespace std;

    typedef long ll;
    ll n,m,R;
    double a, b, c, l, r, delta;
    int cnt[10000009];

    void Init ( ll x, ll y, ll z, ll vx, ll vy, ll vz )
    {
    a = vx * vx + vy * vy + vz * vz;
    b = 2 * x * vx + 2 * y * vy + 2 * z * vz;
    c = x * x + y * y + z * z - R * R;
    delta = b * b - 4 * a * c;
    l = ( -b - sqrt ( delta ) ) / ( 2 * a );
    r = ( -b + sqrt ( delta ) ) / ( 2 * a );
    if(r < 0) return;
    if(l < 0) l = 0;
    if(long(l) != l) l = long(l) + 1;
    r = long(r);
    for(int i=l; i<=r; ++i) ++cnt[i];
    }

    void Input()
    {
    cin >> n >> R;
    while(n--){
    ll x, y, z, vx, vy, vz;
    cin >> x >> y >> z >> vx >> vy >> vz;
    Init ( x, y, z, vx, vy, vz );
    }
    }

    void Sol(){
    cin >> m;
    while(m--){
    ll x;
    cin >> x;
    cout << cnt[x] << "\n";
    }
    }

    signed main()
    {
    FastIO;
    Input();
    Sol();
    }

    1 phản hồi