QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110823#3866. Pandemic Restrictionsgigabuffoon#AC ✓479ms3764kbC++203.4kb2023-06-04 02:22:042023-06-04 02:22:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-04 02:22:07]
  • 评测
  • 测评结果:AC
  • 用时:479ms
  • 内存:3764kb
  • [2023-06-04 02:22:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a),end(a)
#define sz(a) int(size(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using vi = vector<int>;
using ll = long long;
using ld = double;
using pll = pair<ll,ll>;

struct Point{
    typedef Point P;
    ld x, y;
    Point(ld x=0, ld y=0): x(x), y(y) {}
    bool operator<(P p) const {
        return tie(x, y) < tie(p.x, p.y);
    }
    P operator+(P p) const { return P(x + p.x, y + p.y); }
    P operator-(P p) const { return P(x - p.x, y - p.y); }
    P operator*(ld d) const { return P(x * d, y * d); }
    P operator/(ld d) const { return P(x / d, y / d); }
    ld dist2() const { return x*x + y*y; }
    ld dist() const { return sqrtl(dist2()); }
};

using P = Point;
using Tri = array<P, 3>;

const int NUM_ITS = 85;
const int MAX_X = 1e4;

// ld gss(ld a, ld b, ld (*f)(ld)) {
template<class F>
ld gss(ld a, ld b, F& f, bool printCoord=false){
    ld r = (sqrt(5) - 1) / 2, eps = 1e-9;
    ld x1 = b - r * (b - a), x2 = a + r * (b - a);
    ld f1 = f(x1), f2 = f(x2);

    // switched to fixed iterations
    while(b - a > eps)
    // for(int it = 0; it < NUM_ITS; ++it)
        if(f1 < f2) {
            b = x2;
            x2 = x1;
            f2 = f1;
            x1 = b - r * (b - a);
            f1 = f(x1);
        } else {
            a = x1;
            x1 = x2;
            f1 = f2;
            x2 = a + r * (b - a);
            f2 = f(x2);
        }
    if(printCoord) cout << a << endl;
    return f(a);
}

pair<ld, ld> getRange(P& A, P& B, P& C, ld x){
    // subproblem to Mag
    ld tAC = (x - A.x) / (C.x - A.x);
    ld y1 = (A + (C - A) * tAC).y, y2;
    if(x <= B.x) {
        ld tAB = (x - A.x) / (B.x - A.x);
        y2 = (A + (B - A) * tAB).y;
    } else {
        ld tBC = (x - B.x) / (C.x - B.x);
        y2 = (B + (C - B) * tBC).y;
    }
    if(y1 > y2) swap(y1, y2);
    return {y1, y2};
}

void solve(){
    Tri initTri;
    for(int i = 0; i < 3; ++i){
        ld x, y;
        cin >> x >> y;
        initTri[i] = P(x, y);
    }

    // takes in triangle, tern searches (x, y), runs getCost(Tri tri, P p)
    auto solveTri = [&](Tri& tri, auto& getCost) -> ld {
        sort(all(tri));

        // tern search x, y
        ld lx = tri[0].x, rx = tri[2].x;

        auto fOfX = [&](ld x) -> ld {
            auto [ly, ry] = getRange(tri[0], tri[1], tri[2], x);

            auto fOfY = [&](ld y) -> ld {
                P p(x, y);
                return getCost(tri, p);
            };

            return gss(ly, ry, fOfY);
        };

        return gss(lx, rx, fOfX);
    };

    auto getSumDistsCost = [&](Tri& tri, P& p) -> ld {
        ld out = 0;
        for(P q : tri) out += (p - q).dist();
        return out;
    };

    auto getHouseCost = [&](Tri& tri, P& p) -> ld {
        ld out = 0;
        for(int i = 0; i < 3; ++i){
            for(int j = i + 1; j < 3; ++j){
                Tri newTri = Tri{tri[i], tri[j], p};
                out = max(out, solveTri(newTri, getSumDistsCost));
            }
        }
        return out;
    };

    ld ans = solveTri(initTri, getHouseCost);

    cout << setprecision(12) << fixed << ans << "\n";
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    // int t; cin >> t; while(t--)
    solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 140ms
memory: 3632kb

input:

0 0
5 0
3 3

output:

5.068613995265

result:

ok found '5.06861', expected '5.06861', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

-1 0
0 0
1 0

output:

2.000000000487

result:

ok found '2.00000', expected '2.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 342ms
memory: 3612kb

input:

0 0
4000 0
6000 7000

output:

9219.544457293516

result:

ok found '9219.54446', expected '9219.54446', error '0.00000'

Test #4:

score: 0
Accepted
time: 374ms
memory: 3688kb

input:

-10000 -10000
0 -10000
10000 10000

output:

28284.271247462639

result:

ok found '28284.27125', expected '28284.27125', error '0.00000'

Test #5:

score: 0
Accepted
time: 346ms
memory: 3756kb

input:

8398 7539
1991 -9953
-1155 6332

output:

18628.465127327709

result:

ok found '18628.46513', expected '18628.46513', error '0.00000'

Test #6:

score: 0
Accepted
time: 173ms
memory: 3572kb

input:

-10000 10000
0 9999
10000 10000

output:

20000.000000000520

result:

ok found '20000.00000', expected '20000.00000', error '0.00000'

Test #7:

score: 0
Accepted
time: 202ms
memory: 3616kb

input:

-10000 9987
0 9998
9937 10000

output:

19937.004238351168

result:

ok found '19937.00424', expected '19937.00424', error '0.00000'

Test #8:

score: 0
Accepted
time: 99ms
memory: 3568kb

input:

10000 10000
9999 10000
10000 9999

output:

1.414213563230

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #9:

score: 0
Accepted
time: 479ms
memory: 3744kb

input:

-10000 -2000
2000 10000
10000 -2000

output:

20274.455978062790

result:

ok found '20274.45598', expected '20274.45598', error '0.00000'

Test #10:

score: 0
Accepted
time: 95ms
memory: 3688kb

input:

0 0
1 0
1 1

output:

1.414213562930

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #11:

score: 0
Accepted
time: 300ms
memory: 3664kb

input:

1231 244
-1233 3424
0 -11

output:

4022.896468964343

result:

ok found '4022.89647', expected '4022.89647', error '0.00000'

Test #12:

score: 0
Accepted
time: 417ms
memory: 3612kb

input:

0 0
10000 0
5000 10000

output:

12474.508357809911

result:

ok found '12474.50836', expected '12474.50836', error '0.00000'

Test #13:

score: 0
Accepted
time: 165ms
memory: 3764kb

input:

0 0
10000 0
5000 1

output:

10000.000000000749

result:

ok found '10000.00000', expected '10000.00000', error '0.00000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

0 0
10000 0
5000 0

output:

10000.000000000422

result:

ok found '10000.00000', expected '10000.00000', error '0.00000'

Test #15:

score: 0
Accepted
time: 395ms
memory: 3752kb

input:

-10000 -10000
10000 -10000
10000 10000

output:

28284.271247462639

result:

ok found '28284.27125', expected '28284.27125', error '0.00000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

10000 10000
9999 9999
9998 9998

output:

2.828427125436

result:

ok found '2.82843', expected '2.82843', error '0.00000'