結果

問題 No.764 浮動点
ユーザー Pachicobue
提出日時 2018-12-12 04:08:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 1,500 ms
コード長 2,005 bytes
コンパイル時間 917 ms
コンパイル使用メモリ 102,868 KB
最終ジャッジ日時 2025-01-06 18:57:19
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <bitset>
using ll = long long;
using ld = long double;
constexpr ld PI = 3.1415926535897932384626433832795028;
int main()
{
    ll N, L;
    std::cin >> N >> L;
    std::vector<ll> l(N + 1);
    for (auto& e : l) { std::cin >> e; }
    if (L > std::accumulate(l.begin(), l.end(), 0)) {
        for (ll i = 0; i < N; i++) { std::cout << 0 << std::endl; }
        return 0;
    }
    auto sect = [&](ll l, ll r) -> ld {
        if (l > r) { std::swap(l, r); }
        if (L <= r - l) { return l * l * PI; }
        if (l + r <= L) { return 0; }
        const ld s1 = std::acos((ld)(L * L + l * l - r * r) / (2 * l * L));
        const ld s2 = std::acos((ld)(L * L - l * l + r * r) / (2 * r * L));
        return l * l * s1 + r * r * s2 - L * l * std::sin(s1);
    };
    auto area = [&](const ll lmin, const ll lmax, const ll rmin, const ll rmax) { return sect(lmax, rmax) - sect(lmax, rmin) - sect(lmin, rmax) + sect
        (lmin, rmin); };
    auto update = [](const ll min, const ll max, const ll d) -> std::pair<ll, ll> {
        if (min >= d) { return {min - d, max + d}; }
        if (max >= d) { return {0, max + d}; }
        return {d - max, max + d};
    };
    std::vector<ll> lmin(N, 0), lmax(N, 0), rmin(N, 0), rmax(N, 0);
    for (ll i = 0; i < N; i++) {
        const ll L = l[i], R = l[N - i];
        const ll lmi = (i == 0 ? 0 : lmin[i - 1]), lma = (i == 0 ? 0 : lmax[i - 1]);
        const auto ln = update(lmi, lma, L);
        lmin[i] = ln.first, lmax[i] = ln.second;
        const ll rmi = (i == 0 ? 0 : rmin[N - i]), rma = (i == 0 ? 0 : rmax[N - i]);
        const auto rn = update(rmi, rma, R);
        rmin[N - i - 1] = rn.first, rmax[N - i - 1] = rn.second;
    }
    //    show(lmin), show(lmax), show(rmin), show(rmax);
    for (ll i = 0; i < N; i++) { std::cout << std::setprecision(16) << area(lmin[i], lmax[i], rmin[i], rmax[i]) << std::endl; }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0