QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562062#1981. Safe DistanceV-ioleTAC ✓24ms4016kbC++202.3kb2024-09-13 14:41:482024-09-13 14:41:50

Judging History

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

  • [2024-09-13 14:41:50]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:4016kb
  • [2024-09-13 14:41:48]
  • 提交

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'