結果

問題 No.2632 Center of Three Points in Lp Norm
コンテスト
ユーザー noya2
提出日時 2024-02-13 20:17:54
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 33 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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