QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719597 | #3594. Weird Flecks, But OK | andahe | AC ✓ | 7ms | 4408kb | C++20 | 2.0kb | 2024-11-07 04:43:34 | 2024-11-07 04:43:34 |
Judging History
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'