QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163659 | #1950. Surveillance | 1e11 | AC ✓ | 2ms | 3788kb | C++20 | 1.4kb | 2023-09-04 13:41:59 | 2023-09-04 13:42:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using dbl = long double;
dbl magic(dbl H, dbl W, dbl h, dbl w){
dbl a = h / (W - w) / w, b = W * h / (W - w);
auto f = [&](dbl t){
return -a * t * t * t / 3 + b * t - t * (-a * t * t + b);
};
return f(w) - (b - H > 0 ? f(sqrtl((b - H) / a)) : 0);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
dbl H, W, h, w;
int n; cin >> n;
vector<pair<int, int>> p(n);
int mxx = -1e9, mnx = 1e9, mxy = -1e9, mny = 1e9;
for (auto& [x, y] : p) {
cin >> x >> y;
mxx = max(mxx, x);
mnx = min(mnx, x);
mxy = max(mxy, y);
mny = min(mny, y);
}
if (n == 4){
cout << (mxx - mnx) * (mxy - mny) << '\n';
return;
}
set<pair<int, int>> s;
for (auto x : {mnx, mxx})
for (auto y : {mny, mxy})
s.insert(make_pair(x, y));
for (auto pp : p)
if (s.find(pp) != s.end())
s.erase(pp);
pair<int, int> missing = *s.begin();
pair<int, int> center;
for (auto& [x, y] : p){
if (x != mxx && x != mnx && y != mxy && y != mny){
center = {x, y};
}
}
W = mxx - mnx, H = mxy - mny;
w = W - abs(missing.first - center.first), h = H - abs(missing.second - center.second);
dbl ans = w * h + magic(H, W, h, w) + magic(W, H, w, h);
cout << fixed << setprecision(20) << ans << '\n';
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3432kb
input:
4 -5 6 -5 -2 10 -2 10 6
output:
120
result:
ok found '120.0000000', expected '120.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
6 627 -788 444 -788 444 -986 -102 -986 -102 -993 627 -993
output:
1597.42268842268842266030
result:
ok found '1597.4226884', expected '1597.4226884', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
6 340 110 340 375 -1000 375 -1000 -135 353 -135 353 110
output:
685643.43814516751433529862
result:
ok found '685643.4381452', expected '685643.4381452', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
6 -182 -316 -182 -286 -672 -286 -672 -353 -580 -353 -580 -316
output:
4677.21852505772103736348
result:
ok found '4677.2185251', expected '4677.2185251', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
6 -745 -431 -374 -431 -374 217 -587 217 -587 411 -745 411
output:
252676.39373556568440903902
result:
ok found '252676.3937356', expected '252676.3937356', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
6 -920 341 -920 227 930 227 930 355 -448 355 -448 341
output:
229417.79463074046748261026
result:
ok found '229417.7946307', expected '229417.7946307', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
6 -939 -133 957 -133 957 334 -69 334 -69 725 -939 725
output:
958691.10477013075967533950
result:
ok found '958691.1047701', expected '958691.1047701', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 -175 108 -21 108 -21 -421 82 -421 82 171 -175 171
output:
9897.55834335796528566931
result:
ok found '9897.5583434', expected '9897.5583434', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
6 -306 -342 -235 -342 -235 170 -89 170 -89 548 -306 548
output:
48748.23223458904109506307
result:
ok found '48748.2322346', expected '48748.2322346', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
6 -349 185 -218 185 -218 392 -825 392 -825 -218 -349 -218
output:
284794.98792696408176539080
result:
ok found '284794.9879270', expected '284794.9879270', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
6 -689 -621 551 -621 551 -30 -291 -30 -291 -506 -689 -506
output:
248993.47303745618850712162
result:
ok found '248993.4730375', expected '248993.4730375', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
4 -836 -551 -719 -551 -719 790 -836 790
output:
156897
result:
ok found '156897.0000000', expected '156897.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
4 276 -742 276 772 -947 772 -947 -742
output:
1851622
result:
ok found '1851622.0000000', expected '1851622.0000000', error '0.0000000'