QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489113#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team1600#TL 1ms4236kbC++236.2kb2024-07-24 18:10:162024-07-24 18:10:16

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 18:10:16]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4236kb
  • [2024-07-24 18:10:16]
  • 提交

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 ...

output:


result: