QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53964 | #75. Build the Perfect House | not_so_organic | AC ✓ | 226ms | 6140kb | C++20 | 3.5kb | 2022-10-06 13:43:35 | 2022-10-06 13:43:37 |
Judging History
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);
}
}
Details
Tip: Click on the bar to expand more detailed information
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'