結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー noya2noya2
提出日時 2024-02-13 20:27:06
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 333 ms / 2,000 ms
コード長 4,440 bytes
コンパイル時間 3,831 ms
コンパイル使用メモリ 252,224 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-02-13 20:27:24
合計ジャッジ時間 17,602 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 324 ms
6,676 KB
testcase_01 AC 298 ms
6,676 KB
testcase_02 AC 321 ms
6,676 KB
testcase_03 AC 203 ms
6,676 KB
testcase_04 AC 231 ms
6,676 KB
testcase_05 AC 236 ms
6,676 KB
testcase_06 AC 317 ms
6,676 KB
testcase_07 AC 333 ms
6,676 KB
testcase_08 AC 306 ms
6,676 KB
testcase_09 AC 260 ms
6,676 KB
testcase_10 AC 308 ms
6,676 KB
testcase_11 AC 265 ms
6,676 KB
testcase_12 AC 285 ms
6,676 KB
testcase_13 AC 264 ms
6,676 KB
testcase_14 AC 291 ms
6,676 KB
testcase_15 AC 300 ms
6,676 KB
testcase_16 AC 274 ms
6,676 KB
testcase_17 AC 324 ms
6,676 KB
testcase_18 AC 262 ms
6,676 KB
testcase_19 AC 304 ms
6,676 KB
testcase_20 AC 257 ms
6,676 KB
testcase_21 AC 305 ms
6,676 KB
testcase_22 AC 268 ms
6,676 KB
testcase_23 AC 287 ms
6,676 KB
testcase_24 AC 282 ms
6,676 KB
testcase_25 AC 288 ms
6,676 KB
testcase_26 AC 289 ms
6,676 KB
testcase_27 AC 285 ms
6,676 KB
testcase_28 AC 283 ms
6,676 KB
testcase_29 AC 302 ms
6,676 KB
testcase_30 AC 295 ms
6,676 KB
testcase_31 AC 286 ms
6,676 KB
testcase_32 AC 254 ms
6,676 KB
testcase_33 AC 258 ms
6,676 KB
testcase_34 AC 110 ms
6,676 KB
testcase_35 AC 229 ms
6,676 KB
testcase_36 AC 295 ms
6,676 KB
testcase_37 AC 303 ms
6,676 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);
        }
        // cout << mi << ' ' << ma << endl;
        return ma - mi;
    };
    ld minscore = 1e30;
    vec ans(0,0);
    vector<int> ids = {0,1,2};
    do {
        array<vec,3> qs = {ps[ids[0]],ps[ids[1]],ps[ids[2]]};
        vec cur = find_center(p,qs);
        ld curscore = score(cur);
        if (minscore > curscore){
            minscore = curscore;
            ans = cur;
        }
    }while(next_permutation(ids.begin(),ids.end()));
    cout << ans.real() << ' ' << ans.imag() << endl;
    // cout << minscore << endl;
}
0