結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー noshi91noshi91
提出日時 2024-02-17 00:39:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,856 bytes
コンパイル時間 2,046 ms
コンパイル使用メモリ 204,076 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-28 23:16:22
合計ジャッジ時間 5,570 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
6,820 KB
testcase_01 WA -
testcase_02 AC 26 ms
6,816 KB
testcase_03 WA -
testcase_04 AC 25 ms
6,816 KB
testcase_05 WA -
testcase_06 AC 26 ms
6,820 KB
testcase_07 WA -
testcase_08 AC 25 ms
6,816 KB
testcase_09 AC 26 ms
6,820 KB
testcase_10 AC 25 ms
6,816 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 25 ms
6,820 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 25 ms
6,820 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 26 ms
6,820 KB
testcase_25 WA -
testcase_26 AC 26 ms
6,816 KB
testcase_27 AC 25 ms
6,816 KB
testcase_28 WA -
testcase_29 AC 26 ms
6,816 KB
testcase_30 AC 25 ms
6,820 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 26 ms
6,816 KB
testcase_34 AC 26 ms
6,816 KB
testcase_35 AC 26 ms
6,816 KB
testcase_36 AC 24 ms
6,820 KB
testcase_37 AC 25 ms
6,820 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;
  }

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

  return 0;
}
0