結果

問題 No.764 浮動点
ユーザー PachicobuePachicobue
提出日時 2018-12-12 04:08:40
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 1,500 ms
コード長 2,005 bytes
コンパイル時間 1,399 ms
コンパイル使用メモリ 103,084 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-25 08:14:21
合計ジャッジ時間 2,177 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 3 ms
4,348 KB
testcase_04 AC 4 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 4 ms
4,348 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 5 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 3 ms
4,348 KB
testcase_12 AC 4 ms
4,348 KB
testcase_13 AC 4 ms
4,348 KB
testcase_14 AC 5 ms
4,348 KB
testcase_15 AC 4 ms
4,348 KB
testcase_16 AC 5 ms
4,348 KB
testcase_17 AC 4 ms
4,348 KB
testcase_18 AC 3 ms
4,348 KB
testcase_19 AC 4 ms
4,348 KB
testcase_20 AC 5 ms
4,348 KB
testcase_21 AC 4 ms
4,348 KB
testcase_22 AC 5 ms
4,348 KB
testcase_23 AC 5 ms
4,348 KB
testcase_24 AC 4 ms
4,348 KB
testcase_25 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0