結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー ir5ir5
提出日時 2024-06-13 01:58:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,757 bytes
コンパイル時間 6,007 ms
コンパイル使用メモリ 141,432 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 01:58:55
合計ジャッジ時間 9,249 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 33 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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 = -1e12, hi = 1e12; // 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;
}
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]);
}
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));
cout << lo << " " << y << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0