結果

問題 No.2438 Double Least Square
ユーザー hiromi_ayase
提出日時 2025-02-19 22:47:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,699 bytes
コンパイル時間 6,631 ms
コンパイル使用メモリ 334,476 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2025-02-19 22:47:44
合計ジャッジ時間 10,386 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 5 WA * 5 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;
      |              ^~
main.cpp: In function ‘int main()’:
main.cpp:127:43: warning: ‘min_i’ may be used uninitialized [-Wmaybe-uninitialized]
  127 |   double mx1 = tan(theta[min(N - 1, min_i + 1)]);
      |                                     ~~~~~~^~~
main.cpp:110:7: note: ‘min_i’ was declared here
  110 |   int min_i;
      |       ^~~~~
main.cpp:129:41: warning: ‘min_j’ may be used uninitialized [-Wmaybe-uninitialized]
  129 |   double mx2 = tan(phi[min(N - 1, min_j + 1)]);
      |                                   ~~~~~~^~~
main.cpp:111:7: note: ‘min_j’ was declared here
  111 |   int min_j;
      |       ^~~~~

ソースコード

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

  int min_i;
  int min_j;
  double min_v = INF;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      double a1 = tan(theta[i]);
      double a2 = tan(phi[j]);
      double v = L(a1, a2);
      if (v < min_v) {
        min_v = v;
        min_i = i;
        min_j = j;
      }
    }
  }

  double mn1 = tan(theta[max(0, min_i - 1)]);
  double mx1 = tan(theta[min(N - 1, min_i + 1)]);
  double mn2 = tan(phi[max(0, min_j - 1)]);
  double mx2 = tan(phi[min(N - 1, min_j + 1)]);

  double ans = search(mn1, mx1, mn2, mx2, 200);
  cout << fixed << setprecision(10) << ans << endl;
}
0