結果

問題 No.2632 Center of Three Points in Lp Norm
ユーザー noya2noya2
提出日時 2024-02-13 20:06:33
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,542 bytes
コンパイル時間 3,173 ms
コンパイル使用メモリ 248,352 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-02-13 20:06:42
合計ジャッジ時間 8,614 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 46 ms
6,676 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 48 ms
6,676 KB
testcase_05 AC 40 ms
6,676 KB
testcase_06 AC 58 ms
6,676 KB
testcase_07 AC 56 ms
6,676 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 48 ms
6,676 KB
testcase_11 WA -
testcase_12 AC 45 ms
6,676 KB
testcase_13 WA -
testcase_14 AC 48 ms
6,676 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 56 ms
6,676 KB
testcase_18 AC 50 ms
6,676 KB
testcase_19 WA -
testcase_20 AC 41 ms
6,676 KB
testcase_21 AC 42 ms
6,676 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 59 ms
6,676 KB
testcase_26 AC 58 ms
6,676 KB
testcase_27 AC 58 ms
6,676 KB
testcase_28 WA -
testcase_29 AC 45 ms
6,676 KB
testcase_30 AC 54 ms
6,676 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 27 ms
6,676 KB
testcase_35 AC 58 ms
6,676 KB
testcase_36 AC 43 ms
6,676 KB
testcase_37 AC 49 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


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);
    };
    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);
    cout << memo_ans.real() << ' ' << memo_ans.imag() << endl;
}
0