QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719597#3594. Weird Flecks, But OKandaheAC ✓7ms4408kbC++202.0kb2024-11-07 04:43:342024-11-07 04:43:34

Judging History

This is the latest submission verdict.

  • [2024-11-07 04:43:34]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 4408kb
  • [2024-11-07 04:43:34]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-12
struct point
{
    double x, y;
}a[100010], o;
double r;
double dis(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
point get_o(point p1, point p2, point p3)
{
    double a1, b1, c1, a2, b2, c2;
    a1 = 2 * (p1.x - p2.x);
    b1 = 2 * (p1.y - p2.y);
    c1 = (p1.x * p1.x - p2.x * p2.x + p1.y * p1.y - p2.y * p2.y);
    a2 = 2 * (p1.x - p3.x);
    b2 = 2 * (p1.y - p3.y);
    c2 = (p1.x * p1.x - p3.x * p3.x + p1.y * p1.y - p3.y * p3.y);
    point ans;
    ans.x = (b2 * c1 - b1 * c2) / (a1 * b2 - b1 * a2);
    ans.y = (c1 * a2 - c2 * a1) / (b1 * a2 - a1 * b2);
    return ans;
}
const int N(5005);
double X[N], Y[N], Z[N];
double xx[3][N], yy[3][N];
int main()
{
    //freopen("1.in","r",stdin);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> X[i] >> Y[i] >> Z[i];
    for(int i= 1; i <= n; ++i)
    {
        xx[0][i] = X[i], yy[0][i] = Y[i];
        xx[1][i] = X[i], yy[1][i] = Z[i];
        xx[2][i] = Y[i], yy[2][i] = Z[i];
    }
    double ans = 2147483640;
    int T = 3;
    while(T --> 0)
    {
    for (int i = 1; i <= n; ++i)
        a[i].x = xx[T][i], a[i].y = yy[T][i];
    random_shuffle(a + 1, a + n + 1);
    o = a[1], r = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (dis(o, a[i]) - r < eps) 
            continue;
        o.x = (a[1].x + a[i].x) / 2;
        o.y = (a[1].y + a[i].y) / 2;
        r = dis(a[1], a[i]) / 2;
        for (int j = 1; j < i; ++j)
        {
            if (dis(o, a[j]) - r < eps) 
                continue;
            o.x = (a[i].x + a[j].x) / 2;
            o.y = (a[i].y + a[j].y) / 2;
            r = dis(a[i], a[j]) / 2;
            for (int k = 1; k < j; ++k)
            {
                if (dis(o, a[k]) - r < eps)
                    continue;
                o = get_o(a[i], a[j], a[k]);
                r = dis(o, a[i]);
            }
        }
    }
    ans = min(ans, r);
    }
    printf("%.10f\n", ans*2);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4016kb

input:

3
1.0 0.0 1.4
-1.0 0.0 -1.4
0.0 1.0 -0.2

output:

2.0000000000

result:

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

Test #2:

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

input:

5
1.4 1.0 0.0
-0.4 -1.0 0.0
-0.1 -0.25 -0.5
-1.2 0.0 0.9
0.2 0.5 0.5

output:

2.0000000000

result:

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

Test #3:

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

input:

8
435.249 -494.71 -539.356
455.823 -507.454 -539.257
423.394 -520.682 -538.858
446.507 -501.953 -539.37
434.266 -503.664 -560.631
445.059 -549.71 -537.501
449.65 -506.637 -513.778
456.05 -499.715 -561.329

output:

49.9998293198

result:

ok found '49.99983', expected '49.99983', error '0.00000'

Test #4:

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

input:

1000
316.667 322.677 -304.77
315.164 324.611 -306.964
314.498 323.169 -305.335
316.351 324.314 -303.093
316.459 323.113 -308.607
315.298 323.223 -308.678
314.523 324.616 -304.568
315.904 322.836 -304.76
316.635 324.611 -305.856
318.017 324.31 -305.868
315.815 324.613 -306.005
316.247 324.591 -305.62...

output:

9.9996906644

result:

ok found '9.99969', expected '9.99969', error '0.00000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

100
379.075 874.8 -615.221
353.37 875.855 -701.928
378.64 874.035 -647.026
341.969 874.738 -629.655
366.37 874.189 -637.855
398.826 874.824 -623.125
362.408 874.365 -636.885
398.437 874.917 -618.666
410.135 875.033 -649.607
391.667 874.589 -620.111
381.353 876.007 -623.489
358.552 874.198 -630.645
4...

output:

90.0002730055

result:

ok found '90.00027', expected '90.00027', error '0.00000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

100
419.248 -126.167 -123.758
447.088 -422.086 -124.429
568.606 -89.2387 -125.546
459.091 -25.556 -125.617
538.301 -25.6195 -123.663
485.169 -111.069 -125.594
561.241 -111.96 -123.725
540.03 -128.293 -124.649
532.645 -82.8724 -125.596
479.398 -138.095 -123.662
306.439 -181.341 -124.603
643.097 -186....

output:

419.9993449149

result:

ok found '419.99934', expected '419.99934', error '0.00000'

Test #7:

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

input:

100
200.626 736.839 895.973
161.956 737.269 891.832
202.904 737.16 915.413
187.584 737.025 916.874
191.398 736.792 904.898
187.384 738.211 899.186
193.628 736.762 904.285
201.809 737.881 921.002
185.432 737.143 903.122
200.523 737.069 895.035
193.45 736.77 905.163
195.806 737.451 887.269
197.471 736...

output:

42.0000008049

result:

ok found '42.00000', expected '42.00000', error '0.00000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

200
908.637 -420.441 -411.4
933.287 -425.151 -409.78
914.365 -425.554 -411.653
914.638 -402.599 -410.293
959.592 -407.972 -410.874
914.076 -403.061 -410.455
894.655 -418.914 -410.663
892.599 -424.372 -410.561
918.516 -404.732 -411.66
925.085 -483.545 -409.713
921.478 -401.337 -411.68
919.548 -403.85...

output:

90.0000452722

result:

ok found '90.00005', expected '90.00071', error '0.00001'

Test #9:

score: 0
Accepted
time: 7ms
memory: 4152kb

input:

5000
17.5139 -445.201 -21.4186
1.05386 -443.856 -5.02221
34.0622 -445.777 -19.0453
35.2413 -445.593 6.70216
3.85424 -444.968 -31.2191
3.12268 -444.167 -12.6509
10.8215 -444.246 -40.5923
-2.32757 -444.78 -5.34474
14.0153 -445.063 24.0729
12.5706 -445.725 -22.2009
10.7189 -445.783 8.18354
4.4902 -445....

output:

109.9994456672

result:

ok found '109.99945', expected '109.99945', error '0.00000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

5
1.0 0.0 200.0
100.0 0.0 -200.0
50.0 0.0 0.0
25.0 0.0 0.0
75.0 0.0 500.0

output:

99.0000000000

result:

ok found '99.00000', expected '99.00000', error '0.00000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

5
1.0 1.0 200.0
1.0 100.0 -200.0
1.0 50.0 0.0
1.0 25.0 0.0
1.0 75.0 500.0

output:

99.0000000000

result:

ok found '99.00000', expected '99.00000', error '0.00000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

100
650.286 -914.322 284.822
596.616 -860.98 224.858
633.356 -916.937 300.203
616.617 -912.407 302.333
676.923 -870.721 277.192
594.81 -867.401 294.872
613.238 -910.467 289.402
598.187 -857.294 276.72
611.162 -841.785 305.476
642.575 -916.411 297.052
632.683 -916.895 293.008
646.66 -915.503 301.765
...

output:

84.0005339751

result:

ok found '84.00053', expected '84.00053', error '0.00000'

Test #13:

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

input:

1000
-357.801 -564.842 -672.156
-343.077 -571.191 -670.446
-360.526 -568.151 -653.471
-356.634 -567.071 -650.637
-363 -571.421 -657.55
-347.078 -573.059 -673.029
-358.539 -573.112 -651.73
-339.377 -572.185 -661.553
-359.285 -569.961 -671.112
-339.739 -566.241 -664.655
-341.125 -568.221 -667.991
-350...

output:

24.6001171843

result:

ok found '24.60012', expected '24.60012', error '0.00000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

200
656.17 533.341 24.1701
906.154 190.551 299.447
110.202 277.796 346.62
110.798 33.6512 144.815
485.686 564.314 234.491
437.636 559.807 41.2729
595.682 553.096 104.186
907.55 159.928 115.49
211.219 -131.691 60.3633
661.359 -217.795 -493.337
124.64 -3.66596 -25.6501
217.76 451.437 200.037
703.329 5...

output:

823.9995984062

result:

ok found '823.99960', expected '823.99960', error '0.00000'

Test #15:

score: 0
Accepted
time: 6ms
memory: 4408kb

input:

5000
-887.357 -541.321 -559.661
-866.647 -555.553 -706.049
-969.539 -553.557 -604.324
-929.337 -524.245 -564.926
-972.86 -549.337 -658.857
-971.425 -541.483 -663.054
-887.541 -532.174 -712.331
-883.165 -557.739 -711.539
-894.007 -493.625 -713.034
-821.89 -544.137 -636.729
-974.141 -512.428 -654.221
...

output:

155.7741073458

result:

ok found '155.77411', expected '155.77411', error '0.00000'