QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379769#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team004#WA 106ms21140kbC++203.5kb2024-04-06 18:56:072024-04-06 18:56:08

Judging History

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

  • [2024-04-06 18:56:08]
  • 评测
  • 测评结果:WA
  • 用时:106ms
  • 内存:21140kb
  • [2024-04-06 18:56:07]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    double x;
    double y;
    Point() : x{0}, y{0} {}
    Point(double x_, double y_) : x{x_}, y{y_} {}
};

double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

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 double Pi = std::acos(-1.0);

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();

    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<double> cand;
    for (int i = 0; i < N; i++) {
        Point a = p[i], b = p[(i + 1) % N];
        if (cross(a, b) < 0) {
            std::swap(a, b);
        }
        double area = cross(a, b);
        double ab = std::sqrt(dot(a - b, a - b));
        double d = area / ab;
        double ang = std::asin(d / R);
        double oa = std::sqrt(dot(a, a));
        double ob = std::sqrt(dot(b, b));
        double angb = std::acos((ab * ab + ob * ob - oa * oa) / 2 / ab / ob);
        double t1 = std::atan2(b.y, b.x) + (angb - ang);
        double t2 = t1 - (Pi - 2 * ang);
        cand.push_back(t1);
        cand.push_back(t2);
    }
    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;
        }
        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: 1ms
memory: 4212kb

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: 4108kb

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: 3892kb

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: 4252kb

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: 4280kb

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.4249492381

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4216kb

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.5625617660

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4172kb

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: 0ms
memory: 4228kb

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.4944640258

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 106ms
memory: 21140kb

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:

250220612.0000000000

result:

wrong answer 1st numbers differ - expected: '314026591.7801104', found: '250220612.0000000', error = '0.2031865'