QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113236 | #1950. Surveillance | ckiseki# | AC ✓ | 1ms | 3828kb | C++14 | 3.5kb | 2023-06-16 18:56:06 | 2023-06-16 18:56:06 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
#define all(v) begin(v),end(v)
using namespace std;
using P = complex<int64_t>;
using llf = long double;
int64_t cross(P a, P b) {
return imag(conj(a) * b);
}
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
vector<P> p(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
p[i] = {x, y};
}
{
vector<int> colinear(n);
for (int i = 0; i < n; i++) {
int C =
cross(p[(i + 2) % n] - p[(i + 1) % n],
p[(i + 1) % n] - p[(i + 0) % n]);
if (C == 0) {
colinear[ (i + 1) % n ] = true;
}
}
vector<P> q;
for (int i = 0; i < n; i++)
if (!colinear[i])
q.emplace_back(p[i]);
p = q;
}
int pos = -1;
for (int i = 0; i < n; i++) {
int C =
cross(
p[(i + 1) % n] - p[(i + 0) % n],
p[(i + 2) % n] - p[(i + 1) % n]
);
if (C < 0) {
pos = (i + 1) % n;
}
}
if (pos == -1) {
int64_t area = cross(p[1] - p[0], p[2] - p[1]);
cout << area << '\n';
return 0;
}
assert (p.size() == 6);
n = 6;
rotate(p.begin(), p.begin() + pos, p.end());
for (int i = 0; i < n; i++) {
if (i != 3)
p[i] -= p[3];
}
p[3] = {0, 0};
while (true) {
if (real(p[0]) > real(p[3]) && imag(p[0]) > imag(p[3]))
break;
for (int i = 0; i < n; i++) {
p[i] = { imag(p[i]), -real(p[i]) };
}
}
int64_t tot_area = 0;
for (int i = 1; i + 1 < n; i++) {
tot_area += cross(p[i] - p[0], p[i + 1] - p[0]);
}
tot_area /= 2;
debug(tot_area);
// x^2 + (sB/t) * y >= s^2 + sB
llf ans = tot_area;
const auto gao = [](auto p) {
int64_t s = real(p[0]), t = imag(p[0]);
int64_t B = real(p[5]) - s;
int64_t h = imag(p[2]);
debug(s, t, B, h);
{
llf jiao = s * s + s * B - s * B * h / llf(t);
if (jiao >= 0) {
jiao = sqrt(jiao);
// jiao ~ s h + (x^2 - s^2 - sB) / (sB/t)
} else {
jiao = 0;
// 0 ~ s h + (x^2 - s^2 - sB) / (sB/t)
}
llf C = h - (s * s + s * B) / ((s * B) / llf(t));
llf integ = -(jiao*jiao*jiao - s*s*s) / 3 * t / (s*B)
+ C * (s - jiao);
debug(integ);
return integ;
}
};
ans -= gao(p);
debug(ans);
reverse(p.begin() + 1, p.end());
for (auto &pi: p)
pi = { imag(pi), real(pi) };
ans -= gao(p);
cout << fixed << setprecision(20);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3436kb
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: 3640kb
input:
6 627 -788 444 -788 444 -986 -102 -986 -102 -993 627 -993
output:
1597.42268842268842021781
result:
ok found '1597.4226884', expected '1597.4226884', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
6 340 110 340 375 -1000 375 -1000 -135 353 -135 353 110
output:
685643.43814516751376686443
result:
ok found '685643.4381452', expected '685643.4381452', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
6 -182 -316 -182 -286 -672 -286 -672 -353 -580 -353 -580 -316
output:
4677.21852505772103825166
result:
ok found '4677.2185251', expected '4677.2185251', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
6 -745 -431 -374 -431 -374 217 -587 217 -587 411 -745 411
output:
252676.39373556568442324988
result:
ok found '252676.3937356', expected '252676.3937356', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
6 -920 341 -920 227 930 227 930 355 -448 355 -448 341
output:
229417.79463074046742576684
result:
ok found '229417.7946307', expected '229417.7946307', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
6 -939 -133 957 -133 957 334 -69 334 -69 725 -939 725
output:
958691.10477013075978902634
result:
ok found '958691.1047701', expected '958691.1047701', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
6 -175 108 -21 108 -21 -421 82 -421 82 171 -175 171
output:
9897.55834335796528122842
result:
ok found '9897.5583434', expected '9897.5583434', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
6 -306 -342 -235 -342 -235 170 -89 170 -89 548 -306 548
output:
48748.23223458904109861578
result:
ok found '48748.2322346', expected '48748.2322346', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
6 -349 185 -218 185 -218 392 -825 392 -825 -218 -349 -218
output:
284794.98792696408179381251
result:
ok found '284794.9879270', expected '284794.9879270', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3812kb
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: 3440kb
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: 0ms
memory: 3440kb
input:
4 276 -742 276 772 -947 772 -947 -742
output:
1851622
result:
ok found '1851622.0000000', expected '1851622.0000000', error '0.0000000'