QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53964#75. Build the Perfect Housenot_so_organicAC ✓226ms6140kbC++203.5kb2022-10-06 13:43:352022-10-06 13:43:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 13:43:37]
  • 评测
  • 测评结果:AC
  • 用时:226ms
  • 内存:6140kb
  • [2022-10-06 13:43:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

struct Point {
  ld x, y;
  Point(ld x, ld y) : x(x), y(y) {}
  Point() {}
  Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
  Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
  Point rot_ccw() { return Point(-y, x); }
  Point normalize() { return Point(x / magnitude(), y / magnitude()); }
  Point scale(ld f) { return Point(x * f, y * f); }
  ld cross(const Point& p) const { return x * p.y - y * p.x; }
  Point negate() { return Point(-x, -y); }
  bool operator<(const Point& p) const { return cross(p) > 0; }
  ld magnitude() const { return sqrt(x * x + y * y); }
  inline bool is_first_quad() { return x >= 0 && y >= 0; }
};

array<Point, 2> points_of_tangency(ld radius, const Point& from_point) {
  ld a = radius, b = from_point.magnitude();
  ld th = acos(a / b);
  ld d = atan2(from_point.y, from_point.x);
  ld d1 = d + th, d2 = d - th;
  Point p1 = Point(a * cos(d1), a * sin(d1));
  Point p2 = Point(a * cos(d2), a * sin(d2));
  return array<Point, 2>{p1, p2};
}

vector<Point> points;

bool possible(ld side) {
  ld half_side = side / 2L;
  ld half_diagonal = half_side * sqrt(2);

  vector<pair<Point, bool>> events;

  int inside = 0;

  for (Point& p : points) {
    if (p.magnitude() < half_side) return false;
    if (p.magnitude() > half_diagonal) continue;

    // Points of tangency from p to the inscribed circle inside the square.
    auto [t1, t2] = points_of_tangency(half_side, p);

    // Vectors that reach a square vertex when added to the points of tangency.
    Point u = (p - t1).normalize().scale(half_side);
    Point v = (p - t2).normalize().scale(half_side);

    // Radial sweep is [0, 90] degrees, so find the ones in the first quadrant.
    Point event1 = (t1 + u).is_first_quad() ? (t1 + u) : (t1 + u.negate());
    Point event2 = (t2 + v).is_first_quad() ? (t2 + v) : (t2 + v.negate());

    if (event2 < event1) swap(event1, event2);

    bool point_initially_inside = p.y < half_diagonal - p.x;

    // When it starts inside the square, it will exit and then enter again.
    // When it starts outside the square, it will enter and then exit.
    if (point_initially_inside) {
      inside++;
      events.push_back(make_pair(event1, false));
      events.push_back(make_pair(event2, true));
    } else {
      events.push_back(make_pair(event1, true));
      events.push_back(make_pair(event2, false));
    }
  }

  if (events.empty()) return true;

  sort(events.begin(), events.end(),
       [](const pair<Point, bool>& a, const pair<Point, bool>& b) {
         return a.first < b.first;
       });

  // It's possible to build the square if there's at least one rotation with no
  // points inside.
  // Radial sweep of square diagonal, from 0 to 90 degrees.
  for (pair<Point, bool> ev : events) {
    auto [_, enter] = ev;
    inside += enter ? 1 : -1;
    if (inside == 0) return true;
  }

  return false;
}

int main() {
  int N;

  while (scanf("%d", &N) == 1) {
    points.clear();

    while (N--) {
      Point p;
      cin >> p.x >> p.y;
      points.push_back(p);
    }

    for (Point& p : points)
      while (!p.is_first_quad()) p = p.rot_ccw();

    ld left = 0;
    ld right = 1e9 * sqrt(2) * 100;

    while (right - left > 0.00001L) {
      ld mid = (left + right) / 2L;
      if (possible(mid))
        left = mid;
      else
        right = mid;
    }

    printf("%.4Lf\n", 4 * left);
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3880kb

input:

1
0 1

output:

8.0000

result:

ok single line: '8.0000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

1
737150196 19121149

output:

5899185190.1193

result:

ok single line: '5899185190.1193'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3876kb

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

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

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: 3ms
memory: 3912kb

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: 191ms
memory: 6124kb

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: 209ms
memory: 6140kb

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: 226ms
memory: 6120kb

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

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

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: 2ms
memory: 3864kb

input:

2
10 4
-5 -8

output:

74.9634

result:

ok single line: '74.9634'

Test #13:

score: 0
Accepted
time: 7ms
memory: 4160kb

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: 5ms
memory: 4088kb

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: 132ms
memory: 6116kb

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: 183ms
memory: 6120kb

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: 183ms
memory: 6124kb

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: 165ms
memory: 6112kb

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: 19ms
memory: 4180kb

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: 4ms
memory: 4096kb

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: 2ms
memory: 3888kb

input:

3
10 -3
3 -10
6 9

output:

76.8603

result:

ok single line: '76.8603'