QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114751 | #75. Build the Perfect House | Yunan | AC ✓ | 815ms | 7568kb | C++14 | 2.6kb | 2023-06-23 14:39:40 | 2023-06-23 14:39:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps = 1e-9;
const ld pi = acos(- 1);
bool leq(ld a, ld b) {
return a <= b + eps;
}
struct point {
int x, y;
point() {}
point(int _x, int _y) {
x = _x, y = _y;
}
point operator - (point p) {
return point(x - p.x, y - p.y);
}
ld norm() {
return hypot(x, y);
}
};
int n;
vector <point> vecP;
void Task() {
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
if (fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
}
ld Angle(ld a) {
while (a < 0) {
a += pi / 2;
}
while (a > pi / 2) {
a -= pi / 2;
}
return a;
}
bool Check(ld m) {
vector <pair <ld, bool>> vecInterval;
for (int i = 0; i < n; ++i) {
ld d = (vecP[i] - point(0, 0)).norm();
if (leq(m * sqrt(2), d)) {
vecInterval.push_back({0, true});
vecInterval.push_back({pi / 2, false});
} else {
ld a = atan2(vecP[i].y, vecP[i].x);
vector <ld> vecL = {Angle(- a), Angle(asin(m / d) - a)};
vector <ld> vecR = {Angle(acos(m / d) - a), Angle(pi / 2 - a)};
for (int j = 0; j < 2; ++j) {
if (leq(vecL[j], vecR[j])) {
vecInterval.push_back({vecL[j], true});
vecInterval.push_back({vecR[j], false});
} else {
vecInterval.push_back({0, true});
vecInterval.push_back({vecR[j], false});
vecInterval.push_back({vecL[j], true});
vecInterval.push_back({pi / 2, false});
}
}
}
}
sort(vecInterval.begin(), vecInterval.end());
int status = 0;
for (int i = 0; i < vecInterval.size(); ++i) {
if (vecInterval[i].second) {
status++;
if (status == n) {
return true;
}
} else {
status--;
}
}
return false;
}
void Solve() {
cin >> n;
vecP.resize(n);
ld l = 0, r = 1e9;
for (int i = 0; i < n; ++i) {
cin >> vecP[i].x >> vecP[i].y;
r = min(r, (vecP[i] - point(0, 0)).norm());
}
for (int loop = 0; loop <= 100; ++loop) {
ld m = (l + r) / 2;
if (Check(m)) {
l = m;
} else {
r = m;
}
}
cout << fixed << setprecision(4) << l * 8;
}
int main() {
Task();
Solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3908kb
input:
1 0 1
output:
8.0000
result:
ok single line: '8.0000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
1 737150196 19121149
output:
5899185190.1193
result:
ok single line: '5899185190.1193'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
10 966443346 -756724170 -994135047 221603380 -678639837 -178769228 -530862694 752762268 -768046638 -463257882 237914061 265304072 224472503 67786657 -722418124 437150660 280931601 982655876 -100691338 -575414914
output:
1875875227.7538
result:
ok single line: '1875875227.7538'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4020kb
input:
100 -807307593 -329027676 29978288 -862282581 199507100 -804875516 756164111 -476914400 388885868 -607655729 268853606 7189787 882419844 -982342495 814289624 -409509654 -552136630 -393924002 387395089 -390056676 -46897750 824082471 -843687211 -808855940 320898921 362841693 -562978010 945412567 19277...
output:
747010080.6848
result:
ok single line: '747010080.6848'
Test #5:
score: 0
Accepted
time: 134ms
memory: 5088kb
input:
10000 -216971808 -400844991 -733662179 -109297508 -474740941 323301341 -33501332 -26194214 -489374896 -91235544 -241666129 546977023 428695487 -71876660 -919475897 674465201 -312547937 -246492172 -689708208 479300243 924021252 -151522527 905289986 -588504604 -88124297 -253183079 -362469880 91566969 ...
output:
67588490.1808
result:
ok single line: '67588490.1808'
Test #6:
score: 0
Accepted
time: 5ms
memory: 4204kb
input:
100 -80 58 -68 -72 -47 88 -76 -63 6 100 59 -80 84 54 93 37 81 -58 100 6 37 93 100 0 100 -5 25 96 -98 -12 91 -41 54 -84 -87 48 85 -52 -87 -48 -5 100 59 81 -72 -67 48 -86 -90 42 -53 85 -89 -42 18 -97 -72 68 -99 -6 -36 -92 95 -29 -5 -99 69 -72 31 -94 69 73 -80 -57 6 -99 -62 -76 53 85 31 95 0 100 77 -63...
output:
579.2322
result:
ok single line: '579.2322'
Test #7:
score: 0
Accepted
time: 802ms
memory: 7316kb
input:
10000 44782151 89412297 -59689723 80231770 49764021 86738354 -99635125 8534736 6028200 -99818138 82424479 -56623361 40118053 -91599900 78434349 62032675 -59639300 -80269258 -47844666 -87811661 74594114 66601186 -22916641 97338725 58676814 80975498 -66036872 -75094150 -99720603 -7470025 99640468 8472...
output:
565863113.9463
result:
ok single line: '565863113.9463'
Test #8:
score: 0
Accepted
time: 744ms
memory: 7548kb
input:
10000 98035393 19724678 41837446 -90827464 14463253 98948553 -60892748 -79322574 96168392 -27416059 98543165 17007192 -79169286 -61091919 98846219 -15146782 91874996 39484008 -96422504 -26508486 80568024 -59235070 -66178297 -74969539 -84701053 53157601 39599434 -91825290 99526141 -9723545 77171340 -...
output:
565863098.9168
result:
ok single line: '565863098.9168'
Test #9:
score: 0
Accepted
time: 793ms
memory: 7568kb
input:
10000 89073036 45455232 -96619062 25781068 6906430 99761687 -57139877 82067956 89129474 -45342685 -10723273 99424146 -84263892 53848412 -50687136 -86201047 54006864 84162940 99995274 1068858 45846726 88871729 86139033 -50795339 -33696244 -94151438 -74593266 -66601174 90775055 -41951487 -59991546 800...
output:
565862046.4054
result:
ok single line: '565862046.4054'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
10 5 0 3 -3 0 -3 0 4 1 1 4 4 5 -5 -2 -2 0 2 1 0
output:
8.0000
result:
ok single line: '8.0000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4016kb
input:
150 1 1 -2 2 3 -3 -4 -4 5 -5 -6 -6 -7 -7 -8 -8 9 -9 10 -10 -11 11 12 -12 13 13 14 14 -15 15 16 16 17 17 18 -18 19 19 20 20 -21 -21 -22 22 23 23 -24 -24 25 25 26 26 -27 27 28 -28 -29 29 -30 30 -31 -31 -32 -32 -33 -33 -34 34 -35 -35 -36 36 37 37 -38 38 39 -39 -40 40 -41 41 -42 -42 -43 43 -44 44 45 -45...
output:
8.0000
result:
ok single line: '8.0000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
2 10 4 -5 -8
output:
74.9634
result:
ok single line: '74.9634'
Test #13:
score: 0
Accepted
time: 128ms
memory: 4868kb
input:
10000 1 1 2 2 3 -3 4 4 5 5 6 -6 -7 7 -8 8 -9 9 10 -10 11 -11 12 12 -13 -13 -14 14 -15 -15 16 16 17 17 -18 -18 19 19 -20 20 -21 21 -22 -22 -23 23 -24 -24 25 25 26 -26 27 27 -28 -28 -29 -29 -30 30 31 -31 -32 -32 33 33 -34 -34 35 35 36 36 37 37 38 38 -39 -39 40 40 -41 41 -42 42 -43 43 44 44 45 45 46 -4...
output:
8.0000
result:
ok single line: '8.0000'
Test #14:
score: 0
Accepted
time: 114ms
memory: 4804kb
input:
10000 -3292 3292 4399 0 -3105 0 -2695 -2695 1551 1551 2604 0 3188 0 2406 -2406 3235 0 -2522 2522 4504 -4504 -1841 0 -2183 2183 -2644 -2644 0 2628 -2059 -2059 0 1071 1937 1937 2424 0 -1890 -1890 1918 1918 3847 3847 -3654 -3654 -4598 4598 3046 0 93 -93 -630 -630 269 269 0 3164 0 2577 0 370 4693 -4693 ...
output:
8.0000
result:
ok single line: '8.0000'
Test #15:
score: 0
Accepted
time: 740ms
memory: 7136kb
input:
10000 21279 -51236 -60434 -10998 -18182 54006 53036 19267 -29805 43608 -20569 -55557 4406 73624 43414 -31433 36285 -37811 51338 21165 41508 32153 -52663 -19684 37304 -36899 28438 46762 34047 -39813 -6942 64062 -46728 28468 -49803 25717 -13880 57855 -11135 -66102 48527 24307 -148 -70407 27981 -45240 ...
output:
418976.3857
result:
ok single line: '418976.3857'
Test #16:
score: 0
Accepted
time: 785ms
memory: 7192kb
input:
10000 79232 22124 -81804 -15950 5575 89331 -14692 82306 65389 -55482 82213 14927 -23478 78643 -88502 37492 1576 -87078 90202 -8582 33313 92981 -76593 -28034 -1749 87021 -52917 -69085 -5617 85696 76480 28277 -84947 40608 -65049 55714 95137 -31039 21576 -79468 -44587 -80142 -95127 30970 -41060 -84416 ...
output:
566435.3626
result:
ok single line: '566435.3626'
Test #17:
score: 0
Accepted
time: 815ms
memory: 7412kb
input:
10000 99279 -34682 23547 -100730 23575 101038 89340 63828 -67226 -88157 91286 59544 -99028 35942 102013 -13199 71366 -85164 64637 -88942 101113 20548 -88624 -65269 101013 -23774 -59157 -92063 85670 70555 78483 79889 -73712 -83992 -26085 100365 -97952 -38712 66081 -88205 102269 -8149 98933 34204 8669...
output:
633749.2500
result:
ok single line: '633749.2500'
Test #18:
score: 0
Accepted
time: 784ms
memory: 7552kb
input:
10000 45175 -32902 -25386 -50339 -2973 -59386 -16735 -56643 51546 -24380 -27613 -46048 -42496 40152 -49298 26101 -45222 29999 27327 -52784 -49906 25699 -52309 23631 -24039 -51906 -54511 -23545 23628 52312 58829 -8717 20823 54517 -25089 53845 -58003 12657 21962 53722 -55216 19674 -32439 -45222 -45112...
output:
336708.0941
result:
ok single line: '336708.0941'
Test #19:
score: 0
Accepted
time: 188ms
memory: 5316kb
input:
10000 -262345 -32149 -101834 -61209 120876 63329 -280132 18178 -209610 159897 99935 59681 102587 264957 -224065 151571 -97557 -54925 561 276865 -140661 -237415 -217763 -66678 -223135 152208 68608 -211781 72052 -161066 -180104 167973 -256244 117878 -102246 -56788 -143185 163890 33231 -261604 47243 28...
output:
822088.5075
result:
ok single line: '822088.5075'
Test #20:
score: 0
Accepted
time: 126ms
memory: 4944kb
input:
10000 1203192 -1055322 -392161 -1163524 95356 -2138005 -1023942 1954390 -2057400 56960 172182 312711 333081 1694264 2114658 772795 1508610 1269974 1269041 -1280110 1496324 -383794 1247867 -1606982 -889432 -1114821 239274 -2178741 765627 -2117717 972480 1163287 -1186709 394002 2074105 -31677 366027 1...
output:
843684.2737
result:
ok single line: '843684.2737'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
3 10 -3 3 -10 6 9
output:
76.8603
result:
ok single line: '76.8603'