QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379833 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team004# | TL | 314ms | 20116kb | C++20 | 2.9kb | 2024-04-06 19:23:22 | 2024-04-06 19:23:24 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct Point {
long double x;
long double y;
Point() : x{0}, y{0} {}
Point(long double x_, long double y_) : x{x_}, y{y_} {}
};
long double dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
long double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
Point operator+(Point a, Point b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator-(Point a, Point b) {
return Point(a.x - b.x, a.y - b.y);
}
const long double Pi = std::acos(-1.0L);
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, R;
std::cin >> N >> R;
std::cout << std::fixed << std::setprecision(10);
if (N == 1) {
std::cout << 0.0 << "\n";
return 0;
}
std::vector<Point> p(N);
for (int i = 0; i < N; i++) {
int x, y;
std::cin >> x >> y;
p[i] = Point(x, y);
}
std::sort(p.begin(), p.end(),
[&](auto a, auto b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
std::vector<Point> hi, lo;
for (auto p : p) {
while (hi.size() > 1 && cross(hi.back() - hi[hi.size() - 2], p - hi.back()) >= 0) {
hi.pop_back();
}
hi.push_back(p);
while (lo.size() > 1 && cross(lo.back() - lo[lo.size() - 2], p - lo.back()) <= 0) {
lo.pop_back();
}
lo.push_back(p);
}
lo.pop_back();
lo.insert(lo.end(), hi.rbegin(), hi.rend() - 1);
p = lo;
N = p.size();
long double ans = 0;
std::vector<int> sum(N + 1);
for (int i = 0; i < N; i++) {
sum[i + 1] = sum[i] + cross(p[i], p[(i + 1) % N]);
}
ans = sum[N];
std::vector<long double> cand;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j) {
cand.push_back(std::atan2(p[j].x - p[i].x, p[i].y - p[j].y));
}
}
}
std::sort(cand.begin(), cand.end());
int i = 0, j = 0;
for (auto t : cand) {
Point q = Point(R * std::cos(t), R * std::sin(t));
while (cross(p[i] - q, p[(i + 1) % N] - p[i]) < 0) {
i = (i + 1) % N;
}
while (cross(p[i] - q, p[(i - 1 + N) % N] - p[i]) < 0) {
i = (i - 1 + N) % N;
}
while (cross(p[j] - q, p[(j + 1) % N] - p[j]) > 0) {
j = (j + 1) % N;
}
while (cross(p[j] - q, p[(j - 1 + N) % N] - p[j]) > 0) {
j = (j - 1 + N) % N;
}
long double res = sum[N];
if (i > j) {
res -= sum[i] - sum[j];
} else {
res = sum[j] - sum[i];
}
res += cross(p[j], q);
res += cross(q, p[i]);
ans = std::max(ans, res);
}
ans /= 2;
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4208kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.0000000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4208kb
input:
2 100 17 7 19 90
output:
4849.7046444376
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
1 100 13 37
output:
0.0000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.0000000000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.4249492380
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.5625617661
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.5954999579
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4064kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.4944640259
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: 0
Accepted
time: 314ms
memory: 20116kb
input:
1000 10000 -9998 -136 -9996 -245 -9995 -280 -9993 -347 -9991 -397 -9989 -440 -9985 -525 -9984 -545 -9983 -564 -9981 -599 -9979 -632 -9973 -721 -9971 -747 -9966 -810 -9963 -846 -9957 -916 -9953 -958 -9948 -1008 -9945 -1037 -9938 -1103 -9927 -1196 -9920 -1253 -9913 -1308 -9908 -1346 -9891 -1465 -9874 ...
output:
314026591.7801103538
result:
ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4148kb
input:
2 10000 -9999 0 -9998 -1
output:
12070.5678118655
result:
ok found '12070.567811865', expected '12070.567811865', error '0.000000000'
Test #11:
score: -100
Time Limit Exceeded
input:
1604 10000 2604 -9655 7380 -6748 9963 859 9843 1765 -1452 9894 -2024 9793 -8862 4633 -2604 -9655 9301 3673 9871 -1601 -565 -9984 9640 -2659 9312 3645 -8291 -5591 7879 6158 1301 9915 509 9987 7757 -6311 -9301 -3673 7702 -6378 5415 8407 -9971 761 9023 -4311 -6785 7346 -9852 1714 -9788 -2048 9819 -1894...