結果

問題 No.2632 Center of Three Points in Lp Norm
コンテスト
ユーザー ir5
提出日時 2024-06-13 02:08:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 3,124 bytes
コンパイル時間 3,684 ms
コンパイル使用メモリ 141,564 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-13 02:08:23
合計ジャッジ時間 9,450 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <ranges>
#include <iomanip>
using namespace std;
using ll = long long;

auto range(int n) { return views::iota(0, n); }

template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }
template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }
template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }

#ifdef ONLINE_JUDGE
#define dump(expr) ;
#else
#define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; }
#endif

using ld = long double;

ld p;
vector<ld> vx(3), vy(3);

ld absf(ld x) { return x > 0 ? x : -x; }

ld fun(int i, int j, ld x, ld y) {
  // robust
  return pow(pow(absf(x - vx[i]), p) + pow(absf(y - vy[i]), p), 1.0 / p)
    - pow(pow(absf(x - vx[j]), p) + pow(absf(y - vy[j]), p), 1.0 / p);
}

const ld INF = 1e12;

ld find_y(int i, int j, ld x0) {
  ld lo = -INF, hi = INF;  // sufficient??
  ld lof = fun(i, j, x0, lo);
  ld hif = fun(i, j, x0, hi);

  if (lof > 0 && hif > 0) return -INF;
  if (lof < 0 && hif < 0) return INF;

  for (int it : range(200)) {
    ld y = (lo + hi) / 2;
    ld f = fun(i, j, x0, y);
    if ((f > 0) == (lof > 0)) {
      lo = y;
      lof = f;
    } else {
      hi = y;
      hif = f;
    }
  }

  return lo;
}

ld diff(ld x) {
  auto y01 = find_y(0, 1, x);
  auto y02 = find_y(0, 2, x);
  return y01 - y02;
}

pair<ld, ld> solve() {
  ld lo = -1e6, hi = 1e6;
  ld lod = diff(lo);
  ld hid = diff(hi);

  dump(lod);
  dump(hid);

  for (int it : range(80)) {
    ld x = (lo + hi) / 2;
    ld d = diff(x);
    if ((d > 0) == (lod > 0)) {
      lo = x;
      lod = d;
    } else {
      hi = x;
      hid = d;
    }
  }

  dump(lo);

  ld y = find_y(0, 1, lo);

  dump(fun(0, 1, lo, y));
  dump(fun(0, 2, lo, y));
  dump(fun(1, 2, lo, y));
  return {lo, y};
}

int main() {
  cout << fixed << setprecision(14);

  cin >> p;
  for (int i : range(3)) cin >> vx[i] >> vy[i];

  /*
  {
    ld x0 = 1e6;
    ld y0 = find_y(0, 2, x0);
    dump(y0);
    dump(fun(0, 2, x0, y0));
  }
  */

  if (vx[0] == vx[1]) {
    swap(vx[0], vx[2]);
    swap(vy[0], vy[2]);
  }
  if (vx[0] == vx[2]) {
    swap(vx[0], vx[1]);
    swap(vy[0], vy[1]);
  }

  auto res = solve();

  if (fun(1, 2, res.first, res.second) > 1.0) {
    for (int i : range(3)) swap(vx[i], vy[i]);
    auto res2 = solve();

    if (fun(1, 2, res2.first, res2.second) > 1.0) {
      dump("HOPELESS");
    }

    cout << res2.second << " " << res2.first << endl;
    return 0;
  }

  cout << res.first << " " << res.second << endl;
}
0