結果

問題 No.764 浮動点
ユーザー PachicobuePachicobue
提出日時 2018-12-12 04:12:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 1,500 ms
コード長 1,985 bytes
コンパイル時間 1,154 ms
コンパイル使用メモリ 104,216 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 03:28:59
合計ジャッジ時間 2,103 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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