結果
問題 | No.2632 Center of Three Points in Lp Norm |
ユーザー | ir5 |
提出日時 | 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 |
ソースコード
#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; }#endifusing 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) {// robustreturn 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;}