結果

問題 No.764 浮動点
ユーザー PachicobuePachicobue
提出日時 2018-12-12 04:10:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,957 bytes
コンパイル時間 1,337 ms
コンパイル使用メモリ 103,208 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-25 08:16:17
合計ジャッジ時間 2,257 ms
ジャッジサーバーID
(参考情報)
judge14 / 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 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
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 5 ms
4,348 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 2 ms
4,348 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 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 (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