結果

問題 No.2438 Double Least Square
ユーザー 👑 NachiaNachia
提出日時 2023-08-18 23:20:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,012 bytes
コンパイル時間 1,115 ms
コンパイル使用メモリ 87,536 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-05-06 06:02:27
合計ジャッジ時間 2,245 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,948 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 3 ms
6,944 KB
testcase_23 AC 3 ms
6,940 KB
testcase_24 AC 3 ms
6,940 KB
testcase_25 AC 3 ms
6,944 KB
testcase_26 AC 3 ms
6,940 KB
testcase_27 AC 3 ms
6,944 KB
testcase_28 AC 3 ms
6,940 KB
testcase_29 AC 3 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    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] -= (double)H / 2.0;
    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 Q = [&](){
        vector<double> sXX(N+1), sXY(N+1), sYY(N+1), sX(N+1), sY(N+1), s(N+1);
        rep(i,N) sXX[i+1] = sXX[i] + X[i] * X[i];
        rep(i,N) sXY[i+1] = sXY[i] + X[i] * Y[i];
        rep(i,N) sYY[i+1] = sYY[i] + Y[i] * Y[i];
        rep(i,N) sX[i+1] = sX[i] + X[i];
        rep(i,N) sY[i+1] = sY[i] + Y[i];
        rep(i,N) s[i+1] = s[i] + 1;
        vector<double> res(N+1);
        auto rangeq = [&](int r) -> double {
            if(r <= 1) return 0;
            double a = sXY[r] / sXX[r];
            return a*a*sXX[r] - 2*a*sXY[r] + sYY[r];
        };
        rep(i,N+1) res[i] = rangeq(i);
        return res;
    };
    double ans = 1.0e100;
    reverse(Y.begin(), Y.end());
    reverse(X.begin(), X.end());
    rep(i,N) Y[i] -= (double)H / 2;
    auto q0 = Q();
    rep(i,N) Y[i] += (double)H;
    reverse(Y.begin(), Y.end());
    reverse(X.begin(), X.end());
    auto q1 = Q();
    if(N == 1) ans = 0;
    for(int s=1; s<N; s++){
        ans = min(ans, q0[s] + q1[N-s]);
    }
    cout.precision(10);
    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;
0