QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562062 | #1981. Safe Distance | V-ioleT | AC ✓ | 24ms | 4016kb | C++20 | 2.3kb | 2024-09-13 14:41:48 | 2024-09-13 14:41:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define ull unsigned long long
typedef long long ll;
#define lowbit(x) ((x) & -(x))
const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 1e6 + 5, M = 5e5 + 10;
typedef pair<int, int> PII;
double T = 1 >> 30;
// double PI = acos(-1);
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
int h, w, n;
struct node
{
double x, y;
} a[1005];
int fa[1010];
int find(int x)
{
if (fa[x] != x)
{
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
{
return;
}
fa[u] = v;
}
int ck(double r)
{
for (int i = 1; i <= n + 4; i++)
{
fa[i] = i;
}
for (int i = 1; i <= n; i++)
{
double x = a[i].x, y = a[i].y;
if (y + r > h)
{
merge(i, n + 1); // 上
}
if (y - r < 0)
{
merge(i, n + 2); // 下
}
if (x + r > w)
{
merge(i, n + 3); // 右
}
if (x - r < 0)
{
merge(i, n + 4); // 左
}
for (int j = 1; j < i; j++)
{
double dis = (a[j].x - x) * (a[j].x - x) + (a[j].y - y) * (a[j].y - y);
if (dis < 4 * r * r)
{
merge(j, i);
}
}
}
if (find(n + 1) == find(n + 2) || find(n + 3) == find(n + 4) || find(n + 1) == find(n + 3) || find(n + 2) == find(n + 4))
{
return 0;
}
return 1;
}
void solve()
{
int i, j;
cin >> w >> h >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i].x >> a[i].y;
}
double l = 0, r = max(h, w);
while (r - l >= 1e-6)
{
double mid = (l + r) / 2.0;
if (ck(mid))
{
l = mid;
}
else
{
r = mid;
}
}
cout << fixed << setprecision(6) << l;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
//system("pause");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
input:
10 10 1 3 3
output:
3.000000
result:
ok found '3.00000', expected '3.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
10 10 1 7 7
output:
3.000000
result:
ok found '3.00000', expected '3.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
20 10 2 10 0 10 10
output:
5.000000
result:
ok found '5.00000', expected '5.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
10 20 4 0 8 3 7 6 9 8 8
output:
2.000000
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
30 20 4 5 14 10 10 14 6.5 17 3
output:
5.000000
result:
ok found '5.00000', expected '5.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
30 20 4 15 17 20 13 24 9.5 27 6
output:
3.201562
result:
ok found '3.20156', expected '3.20156', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
10 10 1 0 0
output:
0.000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
10 10 1 10 10
output:
0.000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
10 10 1 10 9
output:
1.000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3996kb
input:
812517 648294 262 334200.69 30010.85 560168.74 447124.21 123197.49 344164.55 187376.67 505571.96 321589.94 595765.8 131061.45 477641.29 795090.96 419296.78 790864.88 539583.22 646880.22 262857.44 316535.44 520274.9 445046.45 522009.1 780828.68 435788.67 780128.48 287518.84 585820.49 337467.41 499856...
output:
22924.564321
result:
ok found '22924.56432', expected '22924.56432', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
881103 298724 102 825024.72 123175.35 11078.68 202387.89 500479.18 172610.41 393302.81 107825.99 823257.5 29003.64 361095.87 87989.59 612248.44 60291.76 422073.08 162007.84 170137.97 111230.73 276573.02 123635.33 185738.66 199511.76 796035.08 212365.73 807651.22 44545.17 669860.95 139981.51 473274.9...
output:
28692.558831
result:
ok found '28692.55883', expected '28692.55883', error '0.00000'
Test #12:
score: 0
Accepted
time: 18ms
memory: 3956kb
input:
316773 123654 844 293661.3 58844.35 160055.61 121144.19 124351.86 72613.85 52689.32 30201.77 260284.11 15115.19 86679.65 84437.7 186327.59 15469.44 61829.67 76476.9 233950.23 77093.5 8855.2 78656.8 198982.6 13096.98 175066.9 65613.6 257430.3 38778.44 11249.58 19619.46 166664.77 37610.6 188757.77 106...
output:
3458.940000
result:
ok found '3458.94000', expected '3458.94000', error '0.00000'
Test #13:
score: 0
Accepted
time: 14ms
memory: 3896kb
input:
105620 220056 764 86789.2 118848.88 57269.55 93150.41 73457.91 51787.99 476.04 38868.45 93660.62 81388.12 95220.07 6345.34 1040.49 25346.98 77600.47 120252.17 92348.82 30734.22 33864.15 98955.41 92883.46 59515.21 85496.21 26850.04 92452.22 102068.41 18493.17 148236.88 64840.29 16619.03 72767.29 9466...
output:
2856.132650
result:
ok found '2856.13265', expected '2856.13265', error '0.00000'
Test #14:
score: 0
Accepted
time: 21ms
memory: 4016kb
input:
823896 854235 909 633745.52 340395.94 240432.06 574284.51 258805.93 145245.61 805476.43 555182.74 315427.47 834428.06 385995.98 456391.79 169506.97 420822.55 517521.51 798755.18 766824.32 535320.0 581936.83 382363.95 810281.04 850806.28 321869.54 430171.4 707104.98 810222.78 561171.41 435546.4 76029...
output:
13614.960000
result:
ok found '13614.96000', expected '13614.96000', error '0.00000'
Test #15:
score: 0
Accepted
time: 24ms
memory: 3904kb
input:
1000000 1000000 1000 147714.15 501531.23 117620.28 981426.65 13392.6 187894.03 938581.65 835279.74 326177.4 982792.31 594771.41 993467.93 793962.51 340918.44 287496.39 913503.26 77148.1 273700.54 855973.26 33357.46 87648.95 400639.15 860873.5 506945.18 333145.19 219129.37 269739.35 295711.6 697414.8...
output:
6240.500000
result:
ok found '6240.50000', expected '6240.50000', error '0.00000'