Bedao Regular Contest 20 - North Pole - VNOJ: VNOI Online Judge

Bedao Regular Contest 20 - North Pole

Điểm: 0,90 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Dd đang chơi Terraria và vừa mở khóa được vũ khí mới: North Pole.

Mỗi lần sử dụng, vũ khí này bắn một quả cầu tuyết tại vị trí ~(s_i, 0)~ với vector vận tốc ~\vec{v_i} = ({v_x}_i, {v_y}_i)~. Ta giả sử gia tốc trọng trường ~G = 9.8~ và không có lực cản của không khí.

Trên đường bay của quả cầu tuyết sẽ xuất hiện các bông tuyết rơi thẳng đứng và khi rơi xuống sẽ gây sát thương. Quả cầu tuyết biến mất khi chạm đất. Trong bài toán này, có vô số bông tuyết được tạo ra, nghĩa là nếu người chơi đứng dưới đường bay của một quả cầu tuyết thì chắc chắn sẽ bị sát thương.

Demo của vũ khí North Pole.

Yêu cầu: Tính tổng diện tích trên bản đồ mà người chơi đứng ở đó sẽ bị sát thương.

Input

Dòng đầu tiên gồm số nguyên ~n \:(1 \le n \le 1000)~ — số lần Dd sử dụng vũ khí.
~n~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~s_i, {v_x}_i, {v_y}_i \:(0 \le s_i \le 10^9, 1 \le {v_x}_i, {v_y}_i \le 1000)~ — tọa độ và vận tốc của cầu tuyết thứ ~i~.

Output

In ra một dòng duy nhất chứa 1 số thập phân — đáp án của bài toán. Đáp án được chấp nhận nếu sai số không quá ~10^{-6}~.

Scoring

Subtask	Điểm	Giới hạn
1	~15\%~	Không có quỹ đạo của 2 cầu tuyết nào giao nhau hoặc nằm trong nhau.
2	~25\%~	~n \le 100~
3	~60\%~	Không có ràng buộc gì thêm.

Sample Input 1

1
0 1 1

Sample Output 1

0.0069415521

Sample Input 2

2
0 3 5
2 5 2

Sample Output 2

2.7463907059

Notes

Quỹ đạo cầu tuyết trong ví dụ 1.

Quỹ đạo các cầu tuyết trong ví dụ 2.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-2

phonglll đã bình luận lúc 23, Tháng 9, 2024, 14:49

include <bits/stdc++.h> // QioCas

define FOR(i,l,r) for(int i=(l); i<=(r); ++i)

define REP(i,l,r) for(int i=(l); i<(r); ++i)

define FORD(i,r,l) for(int i=(r); i>=(l); --i)

define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)

ifdef LOCAL

include </home/cas/Cp/Lib/debug.h>

else

define console(...) void(10062006)

endif

using namespace std; using ll = long long;

const int N = 1003; const double G = 9.8; const double EPS = 1e-9;

struct Ball { public: double a() const { return B; } double b() const { return A - 2.00 * B * st; }; double c() const { return B * st * st - A * st; }; double F(double x) const { return B * (x - st) * (x - st) * (x - st) / 3.00 + A * (x - st) * (x - st) / 2.00; } double F(double l, double r) const { return F(r) - F(l); }

void input() {
    cin >> st >> vector.first >>vector.second;
    A = vector.second / vector.first;
    B = - G / (2 * vector.first * vector.first);
    en = st + 2.00 * vector.first * vector.second / G;
}

friend std::vector<double> intersect(const Ball& u, const Ball& v) {
    function<std::vector<double>(std::vector<double>)> load = [&] (std::vector<double> val) {
        std::vector<double> res;
        for(const double& x : val) 
            if(max(u.st, v.st) <= x && x <= min(u.en, v.en)) res.push_back(x);
        return res;
    };
    double a = u.a() - v.a(), b = u.b() - v.b(), c = u.c() - v.c();
    if(a == 0) return (b == 0 ? load({}) : load({-c / b}));
    double delta = b * b - 4.00 * a * c;
    if(delta < 0) return load({});
    if(delta == 0) return load({-b / (2 * a)});
    return load({(-b - sqrt(delta)) / (2 * a), (-b + sqrt(delta)) / (2 * a)});
}

double st, en;
pair&lt;double, double> vector;

private: double A, B; };

struct Compress : vector<double> { void load() { sort(this->begin(), this->end()); this->resize(unique(this->begin(), this->end()) - this->begin()); } int prod(const double& val) { return lower_bound(this->begin(), this->end(), val) - this->begin(); } };

int n; Ball a[N]; Compress cps;

void optimize(double l, double r, int& u, int idx) { if(u == 0 || a[u].F(l, r) < a[idx].F(l, r)) u = idx; }

struct Interval { #define mid ((l + r) >> 1) int IT[1000006 << 2];

void addEvent(int id, int l, int r, double s, double t, int idx) {
    if(cps[l - 1] >= t || cps[r] <= s) return;
    if(s <= cps[l - 1] && cps[r] <= t) {
        optimize(cps[l - 1], cps[r], IT[id], idx);
        return;
    }
    addEvent(id << 1, l, mid, s, t, idx);
    addEvent(id << 1 | 1, mid + 1, r, s, t, idx);
}

double dfs(int id, int l, int r, int best) {
    if(IT[id]) optimize(cps[l - 1], cps[r], best, IT[id]);
    if(l == r) {
        if(best == 0) return 0.00;
        return a[best].F(cps[l - 1], cps[r]);
    }
    return dfs(id << 1, l, mid, best) + dfs(id << 1 | 1, mid + 1, r, best);
}

} event;

int c = 0; double at[7];

inline void add(double x) { if(c > 0 && at[c - 1] == x) return; at[c++] = x; if(c >= 2 && at[c - 2] > at[c - 1]) std::swap(at[c - 1], at[c - 2]); }

bool is_used[N];

int main() { cin.tie(NULL)->syncwithstdio(false); cin >> n; FOR(i, 1, n) a[i].input(); FOR(i, 1, n) { cps.pushback(a[i].st); cps.pushback(a[i].en); } FOR(u, 1, n) FOR(v, u + 1, n) { vector<double> its = intersect(a[u], a[v]); for(const double& x : its) cps.push_back(x); } cps.load(); int m = cps.size();

FOR(u, 1, n) FOR(v, u + 1, n) {
    vector<double> its = intersect(a[u], a[v]);
    if(!its.size()) continue;
    c = 0;
    add(a[u].st); add(a[v].st);
    for(const double& x : its) add(x);
    add(a[u].en); add(a[v].en);

    REP(i, 1, c) {
        int best = 0;
        REP(rot, 0, 2) {
            if(a[u].st <= at[i - 1] && at[i] <= a[u].en) {
                optimize(at[i - 1], at[i], best, u);
            }
            std::swap(u, v);
        }
        if(best) {
            is_used[u] = 1;
            event.addEvent(1, 1, m - 1, at[i - 1], at[i], best);
        }
    }
}
FOR(u, 1, n) {
    if(!is_used[u]) event.addEvent(1, 1, m - 1, a[u].st, a[u].en, u);
}
cout << setprecision(10) << fixed << event.dfs(1, 1, m - 1, 0) << "\n";

return 0;

}

-2

kietjumper đã bình luận lúc 27, Tháng 4, 2025, 8:31

#include <bits/stdc++.h> // QioCas

#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)

#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(10062006)
#endif

using namespace std;
using ll = long long;

const int N = 1003;
const double G = 9.8;
const double EPS = 1e-9;

struct Ball 
{
  public:
    double a() const { return B; }
    double b() const { return A - 2.00 * B * st; };
    double c() const { return B * st * st - A * st; };
    double F(double x) const { return B * (x - st) * (x - st) * (x - st) / 3.00 + A * (x - st) * (x - st) / 2.00; }
    double F(double l, double r) const { return F(r) - F(l); }

    void input() {
        cin >> st >> vector.first >>vector.second;
        A = vector.second / vector.first;
        B = - G / (2 * vector.first * vector.first);
        en = st + 2.00 * vector.first * vector.second / G;
    }

    friend std::vector<double> intersect(const Ball& u, const Ball& v) {
        function<std::vector<double>(std::vector<double>)> load = [&] (std::vector<double> val) {
            std::vector<double> res;
            for(const double& x : val) 
                if(max(u.st, v.st) <= x && x <= min(u.en, v.en)) res.push_back(x);
            return res;
        };
        double a = u.a() - v.a(), b = u.b() - v.b(), c = u.c() - v.c();
        if(a == 0) return (b == 0 ? load({}) : load({-c / b}));
        double delta = b * b - 4.00 * a * c;
        if(delta < 0) return load({});
        if(delta == 0) return load({-b / (2 * a)});
        return load({(-b - sqrt(delta)) / (2 * a), (-b + sqrt(delta)) / (2 * a)});
    }

    double st, en;
    pair < double, double > vector;
  private:
    double A, B;
};

struct Compress : vector<double>
{
    void load() { sort(this->begin(), this->end()); this->resize(unique(this->begin(), this->end()) - this->begin()); }
    int prod(const double& val) { return lower_bound(this->begin(), this->end(), val) - this->begin(); } 
};

int n;
Ball a[N];
Compress cps;

void optimize(double l, double r, int& u, int idx) {
    if(u == 0 || a[u].F(l, r) < a[idx].F(l, r)) 
        u = idx;
}

struct Interval {
  #define mid ((l + r) >> 1)
    int IT[1000006 << 2];

    void addEvent(int id, int l, int r, double s, double t, int idx) {
        if(cps[l - 1] >= t || cps[r] <= s) return;
        if(s <= cps[l - 1] && cps[r] <= t) {
            optimize(cps[l - 1], cps[r], IT[id], idx);
            return;
        }
        addEvent(id << 1, l, mid, s, t, idx);
        addEvent(id << 1 | 1, mid + 1, r, s, t, idx);
    }

    double dfs(int id, int l, int r, int best) {
        if(IT[id]) optimize(cps[l - 1], cps[r], best, IT[id]);
        if(l == r) {
            if(best == 0) return 0.00;
            return a[best].F(cps[l - 1], cps[r]);
        }
        return dfs(id << 1, l, mid, best) + dfs(id << 1 | 1, mid + 1, r, best);
    }
} event;

int c = 0;
double at[7];

inline void add(double x) {
    if(c > 0 && at[c - 1] == x) return;
    at[c++] = x;
    if(c >= 2 && at[c - 2] > at[c - 1]) std::swap(at[c - 1], at[c - 2]);
}

bool is_used[N];

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    FOR(i, 1, n) a[i].input();
    FOR(i, 1, n) {
        cps.push_back(a[i].st);
        cps.push_back(a[i].en);
    }
    FOR(u, 1, n) FOR(v, u + 1, n) {
        vector<double> its = intersect(a[u], a[v]);
        for(const double& x : its) cps.push_back(x);
    }
    cps.load();
    int m = cps.size();


    FOR(u, 1, n) FOR(v, u + 1, n) {
        vector<double> its = intersect(a[u], a[v]);
        if(!its.size()) continue;
        c = 0;
        add(a[u].st); add(a[v].st);
        for(const double& x : its) add(x);
        add(a[u].en); add(a[v].en);

        REP(i, 1, c) {
            int best = 0;
            REP(rot, 0, 2) {
                if(a[u].st <= at[i - 1] && at[i] <= a[u].en) {
                    optimize(at[i - 1], at[i], best, u);
                }
                std::swap(u, v);
            }
            if(best) {
                is_used[u] = 1;
                event.addEvent(1, 1, m - 1, at[i - 1], at[i], best);
            }
        }
    }
    FOR(u, 1, n) {
        if(!is_used[u]) event.addEvent(1, 1, m - 1, a[u].st, a[u].en, u);
    }
    cout << setprecision(10) << fixed << event.dfs(1, 1, m - 1, 0) << "\n";

    return 0;
}

-7

van353735 đã bình luận lúc 2, Tháng 9, 2024, 11:22

=))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

PizzaPasta đã bình luận lúc 25, Tháng 9, 2024, 3:15

cam cha cai mom vao