結果

問題 No.2438 Double Least Square
ユーザー 👑 Nachia
提出日時 2023-08-18 23:20:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,012 bytes
コンパイル時間 3,928 ms
コンパイル使用メモリ 84,976 KB
最終ジャッジ日時 2025-02-16 10:47:43
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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