QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379833#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team004#TL 314ms20116kbC++202.9kb2024-04-06 19:23:222024-04-06 19:23:24

Judging History

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

  • [2024-04-06 19:23:24]
  • 评测
  • 测评结果:TL
  • 用时:314ms
  • 内存:20116kb
  • [2024-04-06 19:23:22]
  • 提交

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

output:


result: