QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113233 | #1950. Surveillance | ckiseki# | WA | 1ms | 3712kb | C++14 | 3.2kb | 2023-06-16 18:46:47 | 2023-06-16 18:46:48 |
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};
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
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: -100
Wrong Answer
time: 1ms
memory: 3712kb
input:
6 627 -788 444 -788 444 -986 -102 -986 -102 -993 627 -993
output:
-nan
result:
wrong output format Expected double, but "-nan" found