QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594824 | #9434. Italian Cuisine | ucup-team4757# | WA | 0ms | 3592kb | C++14 | 2.9kb | 2024-09-28 10:34:03 | 2024-09-28 10:34:04 |
Judging History
answer
# include <bits/stdc++.h>
const int32_t maxn = 100005;
const long double eps = 1e-10;
int32_t n;
struct point {
int64_t x, y;
inline long double len () {
return std::sqrt (x * x + y * y);
}
} center;
inline int64_t operator ^ (const point & a, const point & b) {
return a.x * b.y - b.x * a.y;
}
inline point operator - (const point & a, const point & b) {
return (point) {a.x - b.x, a.y - b.y};
}
int64_t rad = 0;
struct triangle {
point p[3];
inline int64_t size () {
return std::abs ((p[2] - p[1]) ^ (p[0] - p[1]));
}
};
struct polygon {
std::vector <point> p;
inline polygon () {
p.clear ();
}
inline void push_back (const point a) {
p.push_back (a);
}
};
int32_t end[maxn];
inline bool cmp (const int64_t sdis, const long double rdis) {
return rdis + eps > sdis;
}
inline long double dis (const point src, const point des, const point p) {
// std::cerr << ((p - src) ^ (des - src)) << '\n';
return fabs (1.0 * ((p - src) ^ (des - src)) / (des - src).len ());
}
inline bool left (const point src, const point des, const point p) {
return cmp (0, 1.0 * ((p - src) ^ (des - src)) / (des - src).len ());
}
inline int32_t nxt (const int32_t x, const int32_t p = n) {
return x == p ? 1 : x + 1;
}
inline int32_t lst (const int32_t x, const int32_t p = n) {
return x == 1 ? p : x - 1;
}
int64_t sizenow = 0, sizemax = 0;
inline void mfind (const polygon & a, const int32_t p, int32_t & h) {
// std::cerr << "bg " << sizenow << '\n';
// if (p == h) h = nxt (h), sizenow = sizenow + ((triangle) {a.p[h - 1], a.p[lst (h) - 1], a.p[p - 1]}).size (), sizemax = std::max (sizemax, sizenow), std::cerr << "add " << h << ' ' << lst (h) << ' ' << p << '\n';
// std::cerr << "md " << sizenow << '\n';
while (left (a.p[nxt (h) - 1], a.p[p - 1], center) && cmp (rad, dis (a.p[nxt (h) - 1], a.p[p - 1], center)))
h = nxt (h), sizenow = sizenow + ((triangle) {a.p[h - 1], a.p[lst (h) - 1], a.p[p - 1]}).size (), sizemax = std::max (sizemax, sizenow);
// std::cerr << "add " << h << ' ' << lst (h) << ' ' << p << '\n';
end[p] = h;
// std::cerr << "ed " << sizenow << '\n';
}
int32_t x, y, now = 0;
inline void Solve (const int32_t Case) {
polygon a;
std::cin >> n;
center = {0, 0}, rad = 0, now = 1, sizenow = sizemax = 0;
std::cin >> center.x >> center.y >> rad;
for (int i = 1; i <= n; ++ i)
std::cin >> x >> y, a.push_back ({x, y});
for (int i = 1; i <= n; ++ i) {
mfind (a, i, now);
sizenow = sizenow - ((triangle) {a.p[nxt (i) - 1], a.p[i - 1], a.p[now - 1]}).size ();
}
std::cout << sizemax << '\n';
// for (int i = 1; i <= n; ++ i) std::cerr << end[i] << '\n';
}
int32_t T;
int main () {
std::ios::sync_with_stdio (0);
std::cin.tie (0), std::cout.tie (0);
std::cin >> T;
for (int i = 1; i <= T; ++ i) Solve (i);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 5 1 1 1 0 0 1 0 5 0 3 3 0 5 6 2 4 1 2 0 4 0 6 3 4 6 2 6 0 3 4 3 3 1 3 0 6 3 3 6 0 3
output:
5 24 0
result:
ok 3 number(s): "5 24 0"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3592kb
input:
1 6 0 0 499999993 197878055 -535013568 696616963 -535013568 696616963 40162440 696616963 499999993 -499999993 499999993 -499999993 -535013568
output:
286862654137719264
result:
wrong answer 1st numbers differ - expected: '0', found: '286862654137719264'