結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー noya2noya2
提出日時 2024-02-13 20:17:54
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,334 bytes
コンパイル時間 2,970 ms
コンパイル使用メモリ 248,424 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-28 18:36:27
合計ジャッジ時間 10,204 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 163 ms
6,816 KB
testcase_01 AC 128 ms
6,820 KB
testcase_02 AC 150 ms
6,820 KB
testcase_03 AC 94 ms
6,820 KB
testcase_04 AC 111 ms
6,816 KB
testcase_05 AC 93 ms
6,816 KB
testcase_06 AC 159 ms
6,816 KB
testcase_07 AC 151 ms
6,816 KB
testcase_08 AC 144 ms
6,816 KB
testcase_09 AC 109 ms
6,816 KB
testcase_10 AC 120 ms
6,820 KB
testcase_11 AC 128 ms
6,820 KB
testcase_12 AC 129 ms
6,820 KB
testcase_13 AC 112 ms
6,816 KB
testcase_14 AC 125 ms
6,820 KB
testcase_15 AC 142 ms
6,820 KB
testcase_16 AC 116 ms
6,816 KB
testcase_17 AC 145 ms
6,820 KB
testcase_18 AC 131 ms
6,816 KB
testcase_19 AC 145 ms
6,820 KB
testcase_20 AC 120 ms
6,820 KB
testcase_21 AC 142 ms
6,816 KB
testcase_22 AC 113 ms
6,816 KB
testcase_23 AC 131 ms
6,820 KB
testcase_24 AC 139 ms
6,816 KB
testcase_25 AC 131 ms
6,820 KB
testcase_26 AC 137 ms
6,820 KB
testcase_27 AC 130 ms
6,816 KB
testcase_28 WA -
testcase_29 AC 137 ms
6,820 KB
testcase_30 AC 134 ms
6,820 KB
testcase_31 AC 121 ms
6,820 KB
testcase_32 AC 95 ms
6,820 KB
testcase_33 AC 122 ms
6,820 KB
testcase_34 AC 54 ms
6,820 KB
testcase_35 AC 115 ms
6,820 KB
testcase_36 AC 141 ms
6,816 KB
testcase_37 AC 134 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using vec = complex<ld>;


vec find_center(ld p, array<vec,3> ps){
    ld ip = 1/p;
    auto dist = [&](int i, vec v){
        v -= ps[i];
        ld sum = powl(abs(v.real()),p) + powl(abs(v.imag()),p);
        return powl(sum,ip);
    };
    vec memo_vec;
    auto which = [&](vec v){
        ld dmin = 1e30;
        int id = -1;
        for (int i = 0; i < 3; i++){
            ld d = dist(i,v);
            if (dmin > d){
                dmin = d;
                id = i;
            }
        }
        memo_vec = v;
        assert(id != -1);
        return id;
    };
    auto which_bound = [&](vec dir){
        dir /= vec(abs(dir));
        if (which(ps[0]+vec(1e12)*dir) == 0){
            return 0;
        }
        ld le = 0, ri = 1e12;
        int test = 100;
        int pre_w = -1;
        while (test--){
            ld md = (le + ri) / 2;
            int cur_w = which(ps[0]+vec(md)*dir);
            if (cur_w == 0){
                le = md;
            }
            else {
                pre_w = cur_w;
                ri = md;
            }
        }
        assert(pre_w != -1);
        return pre_w;
    };
    vec rev1 = ps[0] + ps[0]-ps[1];
    vec rev2 = ps[0] + ps[0]-ps[2];
    vec dir0 = (rev1 + rev2) * vec(0.5);
    vec dir12 = [&]{
        vec dir1 = ps[1] - ps[0];
        if (which_bound(dir1) != 0){
            return dir1;
        }
        vec dir2 = ps[2] - ps[0];
        if (which_bound(dir2) != 0){
            return dir2;
        }
        abort();
    }();
    // cout << dir0 << ' ' << dir12 << endl;
    int w12 = which(dir12);
    // cout << w12 << endl;
    vec dir21(100,100);
    auto from_to = [&](vec dir1, int w1, vec dir2, int w2){
        ld arg1 = arg(dir1);
        ld arg2 = arg(dir2);
        if (arg2 < arg1){
            arg2 += numbers::pi *2;
        }
        int test = 100;
        while (test--){
            ld arg12 = (arg1 + arg2) / 2;
            vec dirt = vec(cosl(arg12),sinl(arg12));
            int w = which_bound(dirt);
            if (w == w1){
                arg1 = arg12;
            }
            else if (w == w2){
                arg2 = arg12;
            }
            else {
                dir21 = dirt;
                return ;
            }
        }
    };
    from_to(dir0,0,dir12,w12);
    from_to(dir12,w12,dir0,0);
    assert(abs(dir21) < 100);
    // cout << dir21 << endl;
    // cout << which_bound(dir21) << endl;
    vec memo_ans(1e7,1e7);
    auto find12 = [&](vec dir1, int w1, vec dir2, int w2){
        ld arg1 = arg(dir1);
        ld arg2 = arg(dir2);
        if (arg2 < arg1){
            arg2 += std::numbers::pi *2;
        }
        // cout << arg1 << ' ' << arg2 << endl;
        int test = 100;
        while (test--){
            ld arg12 = (arg1 + arg2) / 2;
            vec dirt = vec(cosl(arg12),sinl(arg12));
            int w = which_bound(dirt);
            if (w == 0){
                return ;
            }
            if (w == w1){
                arg1 = arg12;
            }
            else {
                arg2 = arg12;
            }
        }
        which_bound(vec(cosl(arg1),sinl(arg1)));
        memo_ans = memo_vec;
    };
    find12(dir12,w12,dir21,3-w12);
    find12(dir21,3-w12,dir12,w12);
    assert(abs(memo_ans) < 1e7);
    return memo_ans;
}

int main(){
    cout << fixed << setprecision(20);
    ld p; cin >> p;
    ld ip = 1/p;
    array<vec,3> ps;
    for (int i = 0; i < 3; i++){
        ld x, y; cin >> x >> y;
        ps[i] = vec(x,y);
    }
    auto dist = [&](int i, vec v){
        v -= ps[i];
        ld sum = powl(abs(v.real()),p) + powl(abs(v.imag()),p);
        return powl(sum,ip);
    };
    auto score = [&](vec v){
        ld mi = 1e30, ma = -1e30;
        for (int i = 0; i < 3; i++){
            ld d = dist(i,v);
            mi = min(mi,d);
            ma = max(ma,d);
        }
        return ma - mi;
    };
    ld minscore = 1e30;
    vec ans(0,0);
    for (int i = 0; i < 3; i++){
        vec cur = find_center(p,ps);
        ld curscore = score(cur);
        if (minscore > curscore){
            minscore = curscore;
            ans = cur;
        }
        swap(ps[0],ps[1]);
        swap(ps[1],ps[2]);
    }
    cout << ans.real() << ' ' << ans.imag() << endl;
    // cout << minscore << endl;
}
0