結果

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

ソースコード

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 L(double a1, double a2) {
  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 mn = -M_PI / 2;
  double mx = M_PI / 2;
  int iter = 200;

  double l = mn, r = mx;

  double b, t;
  double v1, v2;
  for (int i = 0; i < iter; i++) {
    double theta1 = (l * 2 + r) / 3;
    double theta2 = (l + r * 2) / 3;

    double a11 = tan(theta1);
    double a12 = tan(theta2);

    {
      b = mn, t = mx;
      for (int j = 0; j < iter; j++) {
        double phi1 = (b * 2 + t) / 3;
        double phi2 = (b + t * 2) / 3;

        double a21 = tan(phi1);
        double a22 = tan(phi2);

        if (L(a11, a21) < L(a11, a22)) {
          t = phi2;
        } else {
          b = phi1;
        }
      }
      v1 = L(a11, tan(b));
    }

    {
      b = mn, t = mx;
      for (int j = 0; j < iter; j++) {
        double phi1 = (b * 2 + t) / 3;
        double phi2 = (b + t * 2) / 3;

        double a21 = tan(phi1);
        double a22 = tan(phi2);

        if (L(a12, a21) < L(a12, a22)) {
          t = phi2;
        } else {
          b = phi1;
        }
      }
      v2 = L(a12, tan(b));
    }

    if (v1 < v2) {
      r = theta2;
    } else {
      l = theta1;
    }
  }

  cout << fixed << setprecision(10) << v1 << endl;
}
0