QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#797866#3594. Weird Flecks, But OKLaVuna47#AC ✓8ms5512kbC++203.7kb2024-12-03 20:01:382024-12-03 20:01:39

Judging History

This is the latest submission verdict.

  • [2024-12-03 20:01:39]
  • Judged
  • Verdict: AC
  • Time: 8ms
  • Memory: 5512kb
  • [2024-12-03 20:01:38]
  • Submitted

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif


struct Point {
    double x, y;
};

double dist(const Point& a, const Point& b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

struct Circle {
    Point center;
    double radius;

    bool contains(const Point& p) const {
        return dist(center, p) <= radius + 1e-9;
    }
};

// Circle from two points
Circle make_circle_two_points(const Point& p1, const Point& p2) {
    Point center = {(p1.x + p2.x) / 2.0, (p1.y + p2.y) / 2.0};
    double radius = dist(p1, center);
    return {center, radius};
}

// Circle from three points
Circle make_circle_three_points(const Point& p1, const Point& p2, const Point& p3) {
    double A = p2.x - p1.x, B = p2.y - p1.y;
    double C = p3.x - p1.x, D = p3.y - p1.y;
    double E = A * (p1.x + p2.x) + B * (p1.y + p2.y);
    double F = C * (p1.x + p3.x) + D * (p1.y + p3.y);
    double G = 2 * (A * (p3.y - p2.y) - B * (p3.x - p2.x));

    if (fabs(G) < 1e-9) return {{0, 0}, numeric_limits<double>::max()}; // Collinear points

    Point center = {(D * E - B * F) / G, (A * F - C * E) / G};
    double radius = dist(center, p1);
    return {center, radius};
}

// Welzl's algorithm
Circle welzl(vector<Point>::iterator it, vector<Point>::iterator end, vector<Point> R) {
    if (it == end || R.size() == 3) {
        if (R.empty()) return {{0, 0}, 0};
        if (R.size() == 1) return {R[0], 0};
        if (R.size() == 2) return make_circle_two_points(R[0], R[1]);
        return make_circle_three_points(R[0], R[1], R[2]);
    }

    Point p = *it;
    Circle c = welzl(it + 1, end, R);
    if (c.contains(p)) return c;

    R.push_back(p);
    return welzl(it + 1, end, R);
}

Circle min_enclosing_circle(vector<Point>& points) {
    random_shuffle(points.begin(), points.end());
    return welzl(points.begin(), points.end(), {});
}
int solve()
{
	int n;
	if(!(cin>>n))return 1;
	vector<array<double,3>> A(n);
	FOR(i,0,n)FOR(j,0,3)cin>>A[i][j];
	shuffle(all(A),rnd);
    vector<Point> p1(n), p2(n), p3(n);
    FOR(i,0,n)p1[i]={A[i][0],A[i][1]};
    FOR(i,0,n)p2[i]={A[i][0],A[i][2]};
    FOR(i,0,n)p3[i]={A[i][1],A[i][2]};
    

    Circle c1 = min_enclosing_circle(p1);
    Circle c2 = min_enclosing_circle(p2);
    Circle c3 = min_enclosing_circle(p3);
	double res =min(c1.radius,min(c2.radius,c3.radius));
	cout << fixed << setprecision(10) << 2*res << '\n';
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3908kb

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: 3908kb

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: 4380kb

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: 3964kb

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: 3964kb

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: 1ms
memory: 3932kb

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: 4000kb

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: 8ms
memory: 5512kb

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: 0ms
memory: 3936kb

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: 0ms
memory: 3936kb

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: 4096kb

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: 4340kb

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: 3916kb

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: 8ms
memory: 5436kb

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'