結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー noshi91noshi91
提出日時 2024-02-17 00:42:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,056 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 206,520 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-02-17 00:43:04
合計ジャッジ時間 8,508 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
6,676 KB
testcase_01 RE -
testcase_02 AC 27 ms
6,676 KB
testcase_03 RE -
testcase_04 AC 26 ms
6,676 KB
testcase_05 RE -
testcase_06 AC 26 ms
6,676 KB
testcase_07 RE -
testcase_08 AC 26 ms
6,676 KB
testcase_09 AC 27 ms
6,676 KB
testcase_10 AC 27 ms
6,676 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 AC 27 ms
6,676 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 AC 26 ms
6,676 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 26 ms
6,676 KB
testcase_25 RE -
testcase_26 AC 26 ms
6,676 KB
testcase_27 AC 26 ms
6,676 KB
testcase_28 RE -
testcase_29 AC 26 ms
6,676 KB
testcase_30 AC 26 ms
6,676 KB
testcase_31 RE -
testcase_32 RE -
testcase_33 AC 26 ms
6,676 KB
testcase_34 AC 27 ms
6,676 KB
testcase_35 AC 26 ms
6,676 KB
testcase_36 AC 25 ms
6,676 KB
testcase_37 AC 26 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int main() {
  using f64 = double;
  struct pt {
    f64 x, y;
    pt operator-(const pt& a) const { return pt{ x - a.x, y - a.y }; }
  };

  const f64 eps = 1e-16;

  f64 p;
  std::cin >> p;

  const auto norm = [&](const pt& a) -> f64 {
    if (std::abs(a.x) < eps && std::abs(a.y) < eps)
      return 0;
    f64 ret = 0;
    if (std::abs(a.x) > std::abs(a.y)) {
      return std::abs(a.x) * std::pow(1 + std::pow(std::abs(a.y / a.x), p), 1 / p);
    }
    else {
      return std::abs(a.y) * std::pow(1 + std::pow(std::abs(a.x / a.y), p), 1 / p);
    }
  };

  std::array<pt, 3> t;
  for (auto& [x, y] : t) {
    std::cin >> x >> y;
  }

  while (t[0].x == t[1].x || t[1].x == t[2].x) {
    std::rotate(t.begin(), t.begin() + 1, t.end());
  }

  {
    const pt a0 = t[0] - t[1], a2 = t[2] - t[0];
    if (a0.y / a0.x > a2.y / a2.x) {
      std::swap(t[0], t[2]);
    }
  }

  const auto mid = [&](const pt& a, const pt& b, const f64 y) {
    const auto get = [&](const f64 x) {
      return std::abs(norm(a - pt{ x, y }) - norm(b - pt{ x, y }));
    };
    f64 l = -1e7, r = 1e7;
    for (int i = 0; i < 200; i++) {
      const f64 ll = (l + l + r) / 3, rr = (l + r + r) / 3;
      if (get(ll) < get(rr))
        r = rr;
      else
        l = ll;
    }
    return l;
  };

  const auto get = [&](const f64 y) {
    const f64 x0 = mid(t[0], t[1], y);
    const f64 x2 = mid(t[1], t[2], y);
    if (std::abs(x0) > 1e6) {
      return y < (t[0].y + t[1].y) / 2;
    }
    if (std::abs(x2) > 1e6) {
      return y < (t[1].y + t[2].y) / 2;
    }
    return x0 < x2;
  };

  f64 l = -1e6, r = 1e6;
  for (int i = 0; i < 200; i++) {
    const f64 m = (l + r) / 2;
    (get(m) ? l : r) = m;
  }

  const pt o = pt{ mid(t[0],t[1],l), l };

  {
    const f64 a = norm(t[0] - o);
    const f64 b = norm(t[1] - o);
    const f64 c = norm(t[2] - o);
    assert(std::max({ a,b,c }) - std::min({ a,b,c }) < 1e-8);
  }

  std::cout << std::fixed << std::setprecision(20);
  std::cout << mid(t[0], t[1], l) << " " << l << "\n";

  return 0;
}
0