QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489113 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team1600# | TL | 1ms | 4236kb | C++23 | 6.2kb | 2024-07-24 18:10:16 | 2024-07-24 18:10:16 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = -1, inf = 1000111222;
const ld eps = 1e-10;
bool is_less(ld x, ld y) {
return x + eps < y;
//return x + EPS * max(Real(1), max(abs(x), abs(y))) < y;
}
bool is_equal(ld x, ld y) {
return !is_less(x, y) && !is_less(y, x);
}
bool is_less_equal(ld x, ld y) {
return !is_less(y, x);
}
struct point {
ld x, y;
inline void read () {
int a, b;
cin >> a >> b;
x = a;
y = b;
}
bool half() const {
return (is_less(x, ld(0)) && is_less_equal(y, ld(0))) ||
(is_less_equal(ld(0), x) && is_less(y, ld(0)));
}
};
inline bool cmp (point a, point b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
inline bool cw (point a, point b, point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}
inline bool ccw (point a, point b, point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}
void convex_hull (vector<point> & a) {
if (len(a) <= 1) {
return;
}
sort (a.begin(), a.end(), cmp);
point p1 = a[0], p2 = a.back();
vector<point> up = {p1}, down = {p1};
for (int i = 1; i < len(a); i++) {
if (i == len(a) - 1 || cw (p1, a[i], p2)) {
while (len(up) >= 2 && !cw(up[len(up) - 2], up.back(), a[i])) {
up.pop_back();
}
up.pb(a[i]);
}
if (i == len(a) - 1 || ccw (p1, a[i], p2)) {
while (len(down) >= 2 && !ccw(down[len(down) - 2], down.back(), a[i])) {
down.pop_back();
}
down.pb(a[i]);
}
}
a = up;
for (int i = len(down) - 2; i > 0; i--) {
a.pb(down[i]);
}
}
struct line {
ld a, b, c;
line (ld a, ld b, ld c) : a(a), b(b), c(c) {}
line(const point &A, const point &B) {
a = A.y - B.y;
b = B.x - A.x;
c = -a * A.x - b * A.y;
}
};
struct circle {
point c;
ld r;
};
vector<point> get_intersection_private(ld r, const line &l, bool one) {
auto len = l.a * l.a + l.b * l.b;
if (!one && is_less(r * r * len, l.c * l.c)) {
return {};
}
ld x0 = -l.a * l.c / ld(len), y0 = -l.b * l.c / ld(len);
if (one || is_equal(r * r * len, l.c * l.c)) {
return {{x0, y0}};
}
ld d = r * r - l.c * l.c / ld(len);
ld mult = sqrtl(d / ld(len));
return {{x0 + l.b * mult, y0 - l.a * mult}, {x0 - l.b * mult, y0 + l.a * mult}};
}
line shift(const line &l, point p) {
return line(l.a, l.b, l.c - l.a * p.x - l.b * p.y);
}
vector<point> get_intersection(const circle &c, const line &l, bool one = false) {
auto res = get_intersection_private(c.r, shift(l, point{-c.c.x, -c.c.y}), one);
for (auto &p : res) {
p.x += c.c.x;
p.y += c.c.y;
}
return res;
}
ld vector_product(const point &a, const point &b) {
return a.x * b.y - a.y * b.x;
}
bool ccw(const point &a, const point &b) {
return is_less(ld(0), vector_product(a, b));
}
bool cmp_by_angle(const point &a, const point &b) {
const bool h1 = a.half(), h2 = b.half();
if (h1 != h2) {
return h1 < h2;
}
return ccw(a, b);
}
const ld PI = acos(ld(-1));
inline ld get_angle (const point &p) {
return atan2l(p.y, p.x);
}
ld get_area(const vector<point> &a) {
ld res = 0;
for (int i = 0; i < a.size(); ++i) {
res += (a[(i + 1) % a.size()].x - a[i].x) * (a[i].y + a[(i + 1) % a.size()].y);
}
res /= 2;
return abs(res);
}
inline ld f(ld angle, vector <point> a, ld rad) {
point p;
p.x = rad * cosl(angle);
p.y = rad * sinl(angle);
a.pb(p);
convex_hull(a);
return get_area(a);
}
const ld invphi = (sqrtl(5) - 1) / 2;
inline ld solve (ld L, ld R, vector <point> &a, ld rad) {
for (int it = 0; it < 40; it++) {
ld m2 = L + (R - L) * invphi;
ld m1 = R - (R - L) * invphi;
if (f(m1, a, rad) < f(m2, a, rad)) {
L = m1;
}
else {
R = m2;
}
}
return f((L + R) / 2, a, rad);
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, r;
cin >> n >> r;
vector <point> a(n);
for (auto &i : a) {
i.read();
}
convex_hull(a);
n = len(a);
cout << fixed;
cout.precision(20);
if (n == 1) {
cout << "0\n";
return 0;
}
ld ans = 0;
circle c;
c.r = r;
c.c.x = c.c.y = 0;
vector <point> have;
for (int i = 0; i < n; i++) {
int to = i + 1;
if (to == n) {
to = 0;
}
line l(a[i], a[to]);
auto gg = get_intersection(c, l);
for (auto &x : gg) {
have.pb(x);
}
}
sort(all(have), &cmp_by_angle);
for (int i = 0; i < len(have); i++) {
int to = i + 1;
if (to == len(have)) to = 0;
ld L = get_angle(have[i]);
ld R = get_angle(have[to]);
if (L > R) {
R += 2 * PI;
}
umax(ans, solve(L, R, a, r));
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4136kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.00000000000000000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4172kb
input:
2 100 17 7 19 90
output:
4849.70464443756463879254
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 100 13 37
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4192kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.00000000000000000000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.42494923796039074659
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.56256176601164042950
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4192kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.59549995756242424250
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.49446402583271265030
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: -100
Time Limit Exceeded
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 ...