結果
問題 |
No.2438 Double Least Square
|
ユーザー |
![]() |
提出日時 | 2023-08-15 15:22:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,909 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 203,252 KB |
最終ジャッジ日時 | 2025-02-16 08:21:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; } int main(){ ll n, h; cin >> n >> h; vector<pair<ll,ll>> xys(n); for (int i = 0; i < n; i++) cin >> xys[i].first >> xys[i].second; sort(xys.begin(),xys.end()); ld ans = 1e18; for (int i = 0; i < n; i++){ vector<int> uls(n,0); // 0 : lower, 1 : upper auto [xi, yi] = xys[i]; for (int j = 0; j < n; j++){ auto [xj, yj] = xys[j]; if ((2*yi-h)*xj + h*xi <= 2*xi*yj) uls[j] = 1; } array<ll,3> lv = {0,0,0}, uv = {0,0,0}; auto uadd = [&](int j, ll add_del){ auto [xj, yj] = xys[j]; uv[0] += add_del * (h-yj)*(h-yj); uv[1] += add_del * 2*xj*(h-yj); uv[2] += add_del * xj*xj; }; auto ladd = [&](int j, ll add_del){ auto [xj, yj] = xys[j]; lv[0] += add_del * (-yj)*(-yj); lv[1] += add_del * 2*xj*(-yj); lv[2] += add_del * xj*xj; }; for (int j = 0; j < n; j++){ if (uls[j] == 0){ ladd(j,+1); } else { uadd(j,+1); } } auto eval = [](array<ll,3> ar){ auto [a0, a1, a2] = ar; if (a2 == 0) return ld(0); ld ans = a0; ans -= ld(a1)*a1/(4*a2); return ans; }; chmin(ans,eval(lv)+eval(uv)); for (int j = n-1; j >= 0; j--){ if (uls[j] == 0){ ladd(j,-1); uadd(j,+1); } else { uadd(j,-1); ladd(j,+1); } chmin(ans,eval(lv)+eval(uv)); } } cout << fixed << setprecision(15) << ans << endl; }