結果
問題 | No.764 浮動点 |
ユーザー |
![]() |
提出日時 | 2018-12-12 18:58:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,500 ms |
コード長 | 3,117 bytes |
コンパイル時間 | 784 ms |
コンパイル使用メモリ | 97,580 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-25 03:39:56 |
合計ジャッジ時間 | 1,634 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<iostream>#include<vector>#include<string>#include<cmath>#include<algorithm>#include<functional>#include<numeric>#include<queue>#include<stack>#include<map>#include<unordered_map>#include<set>#include<bitset>#pragma regionusing namespace std;#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)#define rep(i,n) FOR(i,0LL,n)#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)#define rrep(i,n) RFOR(i,0LL,n)#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())#define pb push_back#define endl '\n'typedef long long int ll;typedef vector<ll> vll;typedef vector<vll> vvll;typedef pair<ll, ll> pll;typedef vector<pll> vpll;typedef vector<string> vs;typedef map<ll, ll> MAP;const ll inf = 2222222222222222222LL;const ll mod = 1000000007LL;ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;string s;bool ok;ll dx[9] = { 0,1,-1,0,0,1,1,-1,-1 }, dy[9] = { 0,0,0,1,-1,1,-1,1,-1 };#pragma endregion#define MAX 222222ll a[1111], lsum[1111], rsum[1111], lma[1111], rma[1111];pair<double, double> cross(double r1, double r2) {pair<double, double> p(0, 0);p.first = (m + ((double)r1*r1 - r2 * r2) / m) / 2;p.second = sqrt(r1 * r1 - p.first*p.first);return p;}double area(double r1, double r2) {double ret = 0;if (r1 + r2 <= m) return ret;if (llabs(r1 - r2) >= m) {ret = min(r1, r2)*min(r1, r2)*acos(-1);return ret;}pair<double, double> p = cross(r1, r2);double dist = sqrt(p.first*p.first + p.second*p.second);double rad;if (p.first >= 0) rad = acos(1 - (2 * p.second*p.second / dist / dist));else rad = 2 * acos(-1) - acos(1 - (2 * p.second*p.second / dist / dist));if (p.first >= 0) ret = (rad *r1*r1 - dist * dist* sin(rad)) / 2;else ret = (rad *r1*r1 + dist * dist* sin(acos(1 - (2 * p.second*p.second / dist / dist)))) / 2;dist = sqrt((m - p.first) *(m - p.first) + p.second*p.second);if (p.first <= m) rad = acos(1 - (2 * p.second*p.second / dist / dist));else rad = 2 * acos(-1) - acos(1 - (2 * p.second*p.second / dist / dist));if (p.first <= m) ret += (rad *r2*r2 - dist * dist* sin(rad)) / 2;else ret += (rad *r2*r2 + dist * dist* sin(acos(1 - (2 * p.second*p.second / dist / dist)))) / 2;return ret;}int main(void) {ios::sync_with_stdio(false); cin.tie(0);cout.precision(7);cin >> n;cin >> m;FOR(i, 0, n + 1) cin >> a[i];FOR(i, 1, n + 1) lsum[i] = lsum[i - 1] + a[i - 1];FOR(i, 1, n + 1) lma[i] = max(lma[i - 1], a[i - 1]);RFOR(i, 1, n + 1) rsum[i] = rsum[i + 1] + a[i];RFOR(i, 1, n + 1) rma[i] = max(rma[i + 1], a[i]);FOR(i, 1, n + 1) {double ans = area(lsum[i], rsum[i]);if (lsum[i] - lma[i] < lma[i]) ans -= area(lma[i]*2 - lsum[i],rsum[i]);if (rsum[i] - rma[i] < rma[i]) ans -= area(lsum[i], rma[i]*2 - rsum[i]);if (lsum[i] - lma[i] < lma[i] && rsum[i] - rma[i] < rma[i]) ans += area(lma[i]*2 - lsum[i], rma[i]*2 - rsum[i]);cout << fixed << ans << endl;}return 0;}