結果

問題 No.764 浮動点
コンテスト
ユーザー Pachicobue
提出日時 2018-12-12 03:05:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,980 bytes
コンパイル時間 883 ms
コンパイル使用メモリ 103,448 KB
最終ジャッジ日時 2025-01-06 18:56:55
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <bitset>
using ld = long double;
constexpr ld PI = 3.141592653589793238462;
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 l * l * s1 + r * r * s2 - 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); };
    constexpr int MAX = 1000;
    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, MAX), lmax(N, 0), rmin(N, MAX), 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::fixed << std::setprecision(15) << area(lmin[i], lmax[i], rmin[i], rmax[i]) << std::endl; }
    return 0;
}
0