QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68070 | #75. Build the Perfect House | Yunan | WA | 225ms | 3648kb | C++17 | 2.3kb | 2022-12-14 14:30:08 | 2022-12-14 14:30:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long double pi = acos(- 1);
bool equals(long double a, long double b)
{
return abs(a - b) <= 1e-12;
}
struct point
{
long double x, y;
point() {}
point(const long double &a, const long double &b)
{
x = a, y = b;
}
long double dist(const point &a)
{
return hypot(x - a.x, y - a.y);
}
point rotating(const point &a, const long double &b)
{
long double xx = (x - a.x) * cos(b) - (y - a.y) * sin(b);
long double yy = (x - a.x) * sin(b) + (y - a.y) * cos(b);
return point(xx + a.x, yy + a.y);
}
};
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n;
cin >> n;
vector <point> p(n);
for (int i = 0; i < n; ++i)
cin >> p[i].x >> p[i].y;
long double l = 2.0, r = 1e18;
int cnt = 0;
while (equals(l , r) == false && (++cnt) <= 499)
{
long double m = (l + r) / 2.0;
bool checking = true;
long double left = 0.0, right = pi / 2.0, down = pi / 2.0, up = 0.0;
for (int i = 0; i < n; ++i)
{
long double d = p[i].dist(point(0.0, 0.0));
if (equals(d, m / 2.0) == false && d < m / 2.0)
{
checking = false;
break;
}
if (equals(d, m / sqrt(2.0)) == true || d > m / sqrt(2.0))
continue;
long double angle = atan2(p[i].y, p[i].x);
if (angle < 0)
angle += pi;
if (angle >= pi / 2.0 && angle <= pi)
angle -= pi / 2.0;
long double arccos = acos(m / (2.0 * d));
long double arcsin = asin(m / (2.0 * d));
long double l = m / 2.0;
if (- l < p[i].x && p[i].x < l && - l < p[i].y && p[i].y < l)
{
left = max(left, angle - arccos);
right = min(right, angle + arccos);
if (left > right)
{
checking = false;
break;
}
}
else
{
if (angle <= pi * 0.75)
{
down = min(down, angle + arccos);
up = max(up, angle - arccos + pi / 2.0);
}
else
{
down = min(down, angle - arcsin);
up = max(up, angle - arccos);
}
}
if (left > down && right < up)
{
checking = false;
break;
}
}
if (checking == true)
l = m;
else
r = m;
}
cout << fixed << setprecision(4) << l * 4.0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
1 0 1
output:
8.0000
result:
ok single line: '8.0000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
1 737150196 19121149
output:
5899185190.1193
result:
ok single line: '5899185190.1193'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3620kb
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: 4ms
memory: 3628kb
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: 225ms
memory: 3648kb
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: -100
Wrong Answer
time: 1ms
memory: 3636kb
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:
696.0000
result:
wrong answer 1st lines differ - expected: '579.2322', found: '696.0000'