結果

問題 No.2632 Center of Three Points in Lp Norm
コンテスト
ユーザー noshi91
提出日時 2024-02-17 00:42:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,056 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 198,732 KB
最終ジャッジ日時 2025-02-19 15:13:04
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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