結果

問題 No.2438 Double Least Square
ユーザー hiromi_ayase
提出日時 2025-02-19 22:43:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,452 bytes
コンパイル時間 6,649 ms
コンパイル使用メモリ 333,792 KB
実行使用メモリ 10,532 KB
最終ジャッジ日時 2025-02-19 22:43:32
合計ジャッジ時間 10,370 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from main.cpp:1:
In function ‘constexpr const _Tp& std::min(const _Tp&, const _Tp&) [with _Tp = double]’,
    inlined from ‘double search(double, double, double, double, int)’ at main.cpp:83:13:
/usr/include/c++/13/bits/stl_algobase.h:238:7: warning: ‘v1’ may be used uninitialized [-Wmaybe-uninitialized]
  238 |       if (__b < __a)
      |       ^~
main.cpp: In function ‘double search(double, double, double, double, int)’:
main.cpp:33:10: note: ‘v1’ was declared here
   33 |   double v1, v2;
      |          ^~
In function ‘constexpr const _Tp& std::min(const _Tp&, const _Tp&) [with _Tp = double]’,
    inlined from ‘double search(double, double, double, double, int)’ at main.cpp:83:13:
/usr/include/c++/13/bits/stl_algobase.h:238:7: warning: ‘v2’ may be used uninitialized [-Wmaybe-uninitialized]
  238 |       if (__b < __a)
      |       ^~
main.cpp: In function ‘double search(double, double, double, double, int)’:
main.cpp:33:14: note: ‘v2’ was declared here
   33 |   double v1, v2;
      |              ^~

ソースコード

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;
}

double search(double mn1, double mx1, double mn2, double mx2, int iter) {
  double l = mn1, r = mx1;

  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 = mn2, t = mx2;
      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 = mn2, t = mx2;
      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;
    }
  }
  return min(v1, v2);
}

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];
  }

  if (N <= 2) {
    cout << 0 << endl;
    return 0;
  }

  vector<double> theta(N), phi(N);
  for (int i = 0; i < N; i++) {
    theta[i] = atan2(y[i] - H, x[i]);
    phi[i] = atan2(y[i], x[i]);
  }

  ranges::sort(theta);
  ranges::sort(phi);

  double ans = INF;
  for (int i = 0; i < N - 1; i++) {
    double mn1 = theta[i];
    double mx1 = theta[i + 1];

    for (int j = 0; j < N - 1; j++) {
      double mn2 = phi[j];
      double mx2 = phi[j + 1];

      auto v = search(mn1, mx1, mn2, mx2, 10);
      ans = min(ans, v);
    }
  }

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