結果

問題 No.2438 Double Least Square
ユーザー hiromi_ayase
提出日時 2025-02-19 21:37:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,855 bytes
コンパイル時間 6,199 ms
コンパイル使用メモリ 332,872 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-19 21:37:13
合計ジャッジ時間 10,038 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

int N;
double H;
vector<double> x, y;

double get_a1(double x0, double y0) {
  // y0 = a * x0 + H
  return (y0 - H) / x0;
}

double get_a2(double x0, double y0) {
  // y0 = a * x0
  return y0 / x0;
}

double L(double x0, double y0) {
  double a1 = get_a1(x0, y0);
  double a2 = get_a2(x0, y0);

  double ret = 0;
  for (int i = 0; i < N; i++) {
    double y1 = a1 * x[i] + H;
    double y2 = a2 * x[i];
    ret += min(pow(y1 - y[i], 2), pow(y2 - y[i], 2));
  }
  return ret;
}

// y = a1*x + 10
// y = a2*x

int main() {
  FAST_IO

  cin >> N >> H;
  x.resize(N);
  y.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> x[i] >> y[i];
  }

  double l = 0, r = 1e8;
  double b, t;
  double v1, v2;
  for (int i = 0; i < 100; i++) {
    double c1 = (l * 2 + r) / 3;
    double c2 = (l + r * 2) / 3;

    {
      b = 0, t = 1e8;
      for (int j = 0; j < 100; j++) {
        double d1 = (b * 2 + t) / 3;
        double d2 = (b + t * 2) / 3;

        if (L(c1, d1) < L(c1, d2)) {
          t = d2;
        } else {
          b = d1;
        }
      }
      v1 = L(c1, b);
    }

    {
      b = 0, t = 1e8;
      for (int j = 0; j < 100; j++) {
        double d1 = (b * 2 + t) / 3;
        double d2 = (b + t * 2) / 3;

        if (L(c2, d1) < L(c2, d2)) {
          t = d2;
        } else {
          b = d1;
        }
      }
      v2 = L(c2, b);
    }

    if (v1 < v2) {
      r = c2;
    } else {
      l = c1;
    }
  }

  // (inf, -inf)
  double ans = L(l, b);
  cout << fixed << setprecision(10) << ans << endl;
}
0