QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362707#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team1198#RE 0ms0kbC++205.5kb2024-03-23 16:49:182024-03-23 16:49:19

Judging History

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

  • [2024-03-23 16:49:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-03-23 16:49:18]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

using ld = long double;

struct Vector {
    ld x;
    ld y;

    Vector(ld x = 0, ld y = 0): x(x), y(y) {}
    Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}

    ld sqlen() const { return x * x + y * y; }
    ld len() const { return hypotl(x, y); }
    ld ang() const { return atan2l(y, x); }
    Vector nrm() const { return Vector(-y, x); }
};

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(b, a);
}

Vector operator+(const Vector& a, const Vector& b) {
    return {a.x + b.x, a.y + b.y};
}

Vector operator*(const Vector& a, ld k) {
    return {a.x * k, a.y * k};
}

Vector operator/(const Vector& a, ld k) {
    return {a.x / k, a.y / k};
}

ld operator%(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

ld operator*(const Vector& a, const Vector& b) {
    return a.x * b.x + a.y * b.y;
}

istream& operator>>(istream& in, Vector& v) {
    in >> v.x >> v.y;
    return in;
}

const ld EPS = 1e-9, PI = atan2l(0, -1);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    /// cout.tie(0);

    cout << fixed << setprecision(20);


    int n;
    cin >> n;

    if (n == 1) {
        cout << "0.0";
        return 0;
    }

    ld R;
    cin >> R;
    vector<Vector> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    Vector min_p = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i].x < min_p.x) {
            min_p = arr[i];
        } else if (arr[i].x == min_p.x && arr[i].y < min_p.y) {
            min_p = arr[i];
        }
    }

    sort(arr.begin(), arr.end(), [&](Vector u, Vector v) {
        if (abs((u - min_p) % (v - min_p)) < EPS) {
            return (u - min_p).sqlen() < (v - min_p).sqlen();
        }
        return (u - min_p) % (v - min_p) < 0;
    });

    arr.push_back(arr[0]);
    vector<Vector> st;
    int sz = 0;
    for (Vector p : arr) {
        int threshold = 2;
        if (abs(p.x - min_p.x) < EPS && abs(p.y - min_p.y) < EPS) {
            threshold = 3;
        }
        while (sz >= threshold && (p - st[sz - 2]) % (st[sz - 1] - st[sz - 2]) < EPS) {
            --sz;
            st.pop_back();
        }
        ++sz;
        st.push_back(p);
    }

    st.pop_back();
    vector<Vector> p = st;
    n = p.size();

    /**for (int i = 0; i < n; ++i) {
        cout << p[i].x << " " << p[i].y << endl;
    }*/

    vector<ld> pref(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + (p[i] % p[(i + 1) % n]);
    }

    vector<pair<ld, int>> ev;
    for (int i = 0; i < n; ++i) {
        Vector pt = p[i];
        Vector v = p[(i + 1) % n] - pt;
        ld d2 = (v % pt) * (v % pt) / v.sqlen();
        ld l = sqrtl(max((ld)0, R * R - d2));
        Vector n = v.nrm();
        Vector h = n * (v % pt) / v.sqlen();
        Vector start = h + v * l / v.len();
        Vector fin = h - v * l / v.len();
        ev.push_back({start.ang(), i + 1});
        ev.push_back({fin.ang(), -i - 1});
    }

    sort(ev.begin(), ev.end());
    vector<int> visible(n);
    vector<int> li(n), ri(n);
    for (int i = 0; i < 2 * n; ++i) {
        if (ev[i].second > 0) {
            li[ev[i].second - 1] = i;
        } else {
            ri[-ev[i].second - 1] = i;
        }
    }

    for (int i = 0; i < n; ++i) {
        /// cerr << li[i] << " " << ri[i] << "\n";
        if (li[i] > ri[i]) {
            visible[i] = 1;
        }
    }

    int l = -1, r = -1;
    for (int i = 0; i < n; ++i) {
        int i1 = (i + n - 1) % n;
        if (visible[i] && !visible[i1]) {
            assert(l == -1);
            l = i;
        }
        if (!visible[i] && visible[i1]) {
            assert(r == -1);
            r = i;
        }
    }
    assert(l != -1 && r != -1);
    /// cerr << "start: " << l << " " << r << endl;

    auto get = [&](ld ang) {
        Vector pt = {cosl(ang), sinl(ang)};
        pt = pt * R;
        ld area = p[l] % pt + pt % p[r];
        if (l > r) {
            area += pref[l] - pref[r];
        } else {
            area += pref[n] + pref[l] - pref[r];
        }
        /// cout << ang << ": " << abs(area) << endl;
        /// cout << l << " " << r << endl;
        /// cout << pref[n] << " " << pref[l] << " " << pref[r] << endl;
        return abs(area);
    };

    vector<pair<ld, int>> ev1;
    ev1.push_back({-PI, 0});
    for (auto elem : ev) {
        ev1.push_back(elem);
    }
    ev1.push_back({PI, 0});
    ev = ev1;

    ld ans = 0;

    for (int i = 0; i + 1 < (int)ev1.size(); ++i) {
        ld L = ev[i].first, R = ev[i + 1].first;

        if (l != r) {
            /// cerr << "in L" << endl;
            ans = max(ans, get(L));
            /// cerr << (p[r] - p[l]).nrm().x << " " << (p[r] - p[l]).nrm().y << endl;
            ld M = (p[r] - p[l]).nrm().ang();
            /// cerr << M << endl;
            if (M > L && M < R) {
                ans = max(ans, get(M));
            }
        }

        if (ev[i + 1].second > 0) {
            l = (l - 1 + n) % n;
        } else if (ev[i + 1].second < 0) {
            r = (r - 1 + n) % n;
        }
    }

    cout << ans / 2;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:


result: