結果
問題 | No.2438 Double Least Square |
ユーザー |
👑 ![]() |
提出日時 | 2023-08-19 00:08:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 314 ms / 2,000 ms |
コード長 | 2,717 bytes |
コンパイル時間 | 1,374 ms |
コンパイル使用メモリ | 93,644 KB |
最終ジャッジ日時 | 2025-02-16 11:07:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;int main(){int N; cin >> N;int H; cin >> H;double h = (double)H / 2;vector<double> X(N), Y(N);rep(i,N) cin >> X[i] >> Y[i];vector<int> I(N); rep(i,N) I[i] = i;rep(i,N) Y[i] -= h;sort(I.begin(), I.end(), [&](int l, int r) -> bool {return X[l] * Y[r] - X[r] * Y[l] > 0;});rep(t,2){vector<double> F(N);rep(i,N) F[i] = X[I[i]];swap(X, F);swap(X, Y);}auto XI = X;XI.push_back(0.0);sort(XI.begin(), XI.end());double ans = 1e100;auto xxx = [](double xx, double xy, double yy){return (xx == 0.0) ? 0.0 : (yy - xy*xy/xx);};for(double xc : XI){vector<double> XX0(N+1), XY0(N+1), YY0(N+1);vector<double> XX1(N+1), XY1(N+1), YY1(N+1);vector<double> f(N+1);rep(t,2){vector<double> X0, X1, Y0, Y1;rep(i,N){if(X[i] <= xc){X0.push_back(X[i]);X1.push_back(0);Y0.push_back(Y[i]+h);Y1.push_back(0);} else {X0.push_back(0);X1.push_back(X[i]);Y0.push_back(0);Y1.push_back(Y[i]+h);}}if(t){ swap(X0,X1); swap(Y0,Y1); }rep(i,N) XX0[i+1] = XX0[i] + X0[i] * X0[i];for(int i=N-1; i>=0; i--) f[i] = f[i+1] + X1[i] * X1[i];rep(i,N+1) XX0[i] += f[i];rep(i,N) XY0[i+1] = XY0[i] + X0[i] * Y0[i];for(int i=N-1; i>=0; i--) f[i] = f[i+1] + X1[i] * Y1[i];rep(i,N+1) XY0[i] += f[i];rep(i,N) YY0[i+1] = YY0[i] + Y0[i] * Y0[i];for(int i=N-1; i>=0; i--) f[i] = f[i+1] + Y1[i] * Y1[i];rep(i,N+1) YY0[i] += f[i];swap(XX0,XX1); swap(XY0,XY1); swap(YY0,YY1);h = -h;}for(int s=0; s<=N; s++){double c0 = xxx(XX0[s],XY0[s],YY0[s]);double c1 = xxx(XX1[s],XY1[s],YY1[s]);ans = min(ans, c0 + c1);}}cout.precision(10);fixed(cout);cout << ans << endl;return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;