QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#508120#5588. Eroding Pillarsstasio6WA 60ms14268kbC++142.0kb2024-08-07 03:51:262024-08-07 03:51:26

Judging History

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

  • [2024-08-07 03:51:26]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:14268kb
  • [2024-08-07 03:51:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A,class B> void cmx(A& x, B y) {x=max<A>(x,y);}
template<class A,class B> void cmn(A& x, B y) {x=min<A>(x,y);}
typedef pair<int, int> pii;
typedef vector<int> vi;

int x[1002], y[1002];
vector<vi> kra;
int low[1002], gl[1002], ok;

void dfs(int n, int o) {
    gl[n] = gl[o] + 1;
    low[n] = gl[n];
    for (auto v : kra[n]) {
        if (v == o)
            continue;
        if (gl[v]) {
            cmn(low[n], gl[v]);
            continue;
        }
        dfs(v, n);
        cmn(low[n], low[v]);
        if (n != 0 && low[v] >= gl[n])
            ok = 0;
    }
//    cerr << n << " " << low[n] << " " << gl[n] << "\n";
}

bool check (int n, int d) {
//    cerr << d << "\n";
    ok = 1;
    kra.clear();
    kra.resize(n+1);
    for (int i = 0; i <= n; i++) {
        low[i] = gl[i] = 0;
        for (int j = i + 1; j <= n; j++) {
            if ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= d)
                kra[i].PB(j), kra[j].PB(i);
        }
    }
    dfs(0, 0);
//    cerr << ok << "ok\n";
    return ok;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> dists;
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dists.PB((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
        }
    }
    sort(all(dists));
    int pocz = 0, kon = sz(dists) - 1;
    while (pocz < kon) {
        int sr = (pocz + kon) / 2;
        if (check(n, dists[sr])) {
            kon = sr;
        } else {
            pocz = sr + 1;
        }
    }
    cout << fixed << setprecision(10) << sqrt(dists[pocz]) << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

2
1 1
1 0

output:

1.4142135624

result:

ok found '1.4142136', expected '1.4142136', error '0.0000000'

Test #2:

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

input:

8
1 1
0 1
1 0
2 0
0 2
2 1
1 2
2 2

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #3:

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

input:

1
1000000000 -1000000000

output:

1414213562.3730950356

result:

ok found '1414213562.3730950', expected '1414213562.3730950', error '0.0000000'

Test #4:

score: 0
Accepted
time: 60ms
memory: 13720kb

input:

1000
-197140284 703496508
105426106 -447628446
-321789030 -547969163
-275840107 -183856400
977079157 55081681
562400795 -99876434
-833457368 849631307
427777786 981882
-477648368 423363280
-986742316 -207582454
546089414 986224147
648775399 760817052
-111756907 833096696
-702954343 -487408110
-20831...

output:

129014631.0649484694

result:

ok found '129014631.0649485', expected '129014631.0649485', error '0.0000000'

Test #5:

score: 0
Accepted
time: 45ms
memory: 13532kb

input:

999
-37 59
90 99
-78 -74
84 82
-33 22
-5 14
-37 -35
6 -97
-35 -91
-17 -55
85 -75
-13 9
-87 70
64 74
45 -74
-83 -71
-91 -69
64 -54
-28 37
98 65
28 32
12 83
21 94
-42 -63
-14 22
12 -91
-77 -82
18 -79
97 4
23 25
54 58
56 -39
-82 63
-15 89
-36 96
51 5
-37 54
99 57
5 68
82 -75
30 -71
-82 31
-36 -28
48 98...

output:

12.7279220614

result:

ok found '12.7279221', expected '12.7279221', error '0.0000000'

Test #6:

score: 0
Accepted
time: 48ms
memory: 13712kb

input:

999
23 -84
12 68
-82 94
66 -48
-51 21
-65 -75
-8 83
-23 96
7 -83
-5 30
-46 -39
84 81
-43 45
30 -22
66 -35
-40 1
50 37
-41 -56
18 2
88 -30
-15 -69
89 -16
-94 -40
-73 -63
69 -57
-94 -9
-7 -40
11 -23
-35 74
-82 87
-33 55
-60 37
-15 -68
-1 84
57 -5
-46 57
-30 75
-66 52
-60 49
-81 -56
79 0
14 84
-62 47
2...

output:

12.0415945788

result:

ok found '12.0415946', expected '12.0415946', error '0.0000000'

Test #7:

score: 0
Accepted
time: 51ms
memory: 13560kb

input:

997
689820909 872197007
378062710 -66574440
-176944532 -402500960
-626416632 489298754
-136800206 216455436
-778550826 662442290
791847147 -283748980
205140992 574212402
-942834097 -861224089
835282360 82261161
-580910695 909114837
718944957 -300196729
-345551018 -762335643
-341008263 775846670
8876...

output:

122351709.4959319681

result:

ok found '122351709.4959320', expected '122351709.4959320', error '0.0000000'

Test #8:

score: 0
Accepted
time: 56ms
memory: 14268kb

input:

997
208411906 -972635109
-98072108 457691541
-21432981 100025358
25260912 -117889920
133656678 -623760924
114370818 -533755956
175530188 -819179923
33595291 -156785555
213886197 -998183115
-39015831 182082508
-139507592 651066476
-129054888 602284739
-154761300 722253757
198647581 -927066054
1186318...

output:

17118003.7749864385

result:

ok found '17118003.7749864', expected '17118003.7749864', error '0.0000000'

Test #9:

score: -100
Wrong Answer
time: 50ms
memory: 13988kb

input:

997
1000000000 499352126
945459590 1000000000
-771435961 1000000000
-1000000000 -350227738
-589254335 1000000000
905535137 1000000000
89248404 1000000000
-716290383 1000000000
-1000000000 -131547422
442941577 1000000000
-22966025 1000000000
-907816124 1000000000
178384700 1000000000
-783935630 -1000...

output:

4158.0000000000

result:

wrong answer 1st numbers differ - expected: '1000001278.9881818', found: '4158.0000000', error = '0.9999958'