結果
問題 | No.764 浮動点 |
ユーザー |
![]() |
提出日時 | 2023-07-25 00:27:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 1,500 ms |
コード長 | 3,344 bytes |
コンパイル時間 | 1,098 ms |
コンパイル使用メモリ | 119,960 KB |
最終ジャッジ日時 | 2025-02-15 18:47:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#include <atcoder/segtree>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}template<typename T>class Cumsum{public:Cumsum(vector<T> v): v(v){n = v.size();v_cumsum = vector<T>(n+1, T(0));for(int i = 0; i < n; i++) v_cumsum[i+1] = v_cumsum[i]+v[i];}/*** v[l] + ... + v[r-1]*/T sum(int l, int r){if(r <= l) return T(0);if(r > n) r = n;if(l < 0) l = 0;return v_cumsum[r]-v_cumsum[l];}private:int n;vector<T> v;vector<T> v_cumsum;};double op(double x, double y){return max(x, y);}double e(){return 0;}using Seg = atcoder::segtree<double, op, e>;int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int n; cin >> n;double len; cin >> len;vector<double> l(n+1);for(int i = 0; i < n+1; i++) cin >> l[i];auto cumsum = Cumsum<double>(l);auto common_area = [&](double l, double r){if(l+r <= len) return 0.0;if(l >= len+r) return r*r*M_PI;if(r >= len+l) return l*l*M_PI;double a = acos((len*len+l*l-r*r)/(2*len*l));double b = acos((len*len+r*r-l*l)/(2*len*r));double area = l*l*sin(2*a)/2 + r*r*sin(2*b)/2;// cout << l << ' ' << r << ':' << l*l*a << ' ' << r*r*b << ' ' << area << ' ' << a << ' ' << b << ' ' << l*l*a + r*r*b - area << endl;return l*l*a + r*r*b - area;};// print_vector(l);Seg seg(l);for(int c = 1; c <= n; c++){// if(c == 1 || c == n){// cout << 0 << endl;// continue;// }double l0 = seg.prod(0, c), r0 = seg.prod(c, n+1);double l1 = cumsum.sum(0, c)-l0;double r1 = cumsum.sum(c, n+1)-r0;double l_small = max(l0-l1, 0.0);double l_large = l0+l1;double r_small = max(r0-r1, 0.0);double r_large = r0+r1;// cout << l_small << ' ' << l_large << ' ' << r_small << ' ' << r_large << endl;double ans = common_area(l_large, r_large) - common_area(l_small, r_large) - common_area(l_large, r_small) + common_area(l_small, r_small);cout << ans << endl;}}