QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#508125 | #5588. Eroding Pillars | stasio6 | AC ✓ | 82ms | 14180kb | C++14 | 2.1kb | 2024-08-07 03:59:42 | 2024-08-07 03:59:44 |
Judging History
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);
for (int i = 1; i <= n; i++) {
if (!gl[i])
ok = 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: 3908kb
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: 3772kb
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: 3880kb
input:
1 1000000000 -1000000000
output:
1414213562.3730950356
result:
ok found '1414213562.3730950', expected '1414213562.3730950', error '0.0000000'
Test #4:
score: 0
Accepted
time: 56ms
memory: 13752kb
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: 49ms
memory: 13720kb
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: 53ms
memory: 13720kb
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: 54ms
memory: 13644kb
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: 13936kb
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: 0
Accepted
time: 82ms
memory: 14180kb
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:
1000001278.9881818295
result:
ok found '1000001278.9881818', expected '1000001278.9881818', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
4 1 1 -1 -1 1 -1 -1 1
output:
1.4142135624
result:
ok found '1.4142136', expected '1.4142136', error '0.0000000'