QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#797866 | #3594. Weird Flecks, But OK | LaVuna47# | AC ✓ | 8ms | 5512kb | C++20 | 3.7kb | 2024-12-03 20:01:38 | 2024-12-03 20:01:39 |
Judging History
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'