QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114751#75. Build the Perfect HouseYunanAC ✓815ms7568kbC++142.6kb2023-06-23 14:39:402023-06-23 14:39:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 14:39:41]
  • 评测
  • 测评结果:AC
  • 用时:815ms
  • 内存:7568kb
  • [2023-06-23 14:39:40]
  • 提交

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'