QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122192#4799. Rotate Sum 3IsrothyWA 22ms16448kbC++234.3kb2023-07-09 18:07:392023-07-09 18:07:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-09 18:07:41]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:16448kb
  • [2023-07-09 18:07:39]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>

template<typename T> struct Point {
    T x, y;
    explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
    [[nodiscard]] auto len2() const {
        return x * x + y * y;
    }
    [[nodiscard]] auto len() const {
        return std::sqrt(len2());
    }
};
template<typename T> using Vector = Point<T>;
template<typename T> using Line = std::pair<Point<T>, Point<T>>;

template<typename T, typename U> auto operator+(const Point<T> &a, const Point<U> &b) {
    return Point(a.x + b.x, a.y + b.y);
}
template<typename T, typename U> auto operator-(const Point<T> &a, const Point<U> &b) {
    return Point(a.x - b.x, a.y - b.y);
}
template<typename T, typename U> auto operator*(const Point<T> &a, const U &k) {
    return Point(a.x * k, a.y * k);
}
template<typename T, typename U> auto operator*(const U &k, const Point<T> &a) {
    return Point(a.x * k, a.y * k);
}
template<typename T, typename U> auto operator/(const Point<T> &a, const U &k) {
    return Point(a.x / k, a.y / k);
}
template<typename T, typename U> auto det(const Point<T> &a, const Point<U> &b) {
    return a.x * b.y - a.y * b.x;
}
template<typename T, typename U> auto dot(const Point<T> &a, const Point<U> &b) {
    return a.x * b.x + a.y * b.y;
}
template<typename T>
auto point_line_distance(const Point<T> &p, const Point<T> &a, const Point<T> &b) {
    return std::fabs(det(a - p, b - p) / (a - b).len());
}
template<typename T>
int line_line_intersection(
    const Point<T> &a, const Point<T> &b, const Point<T> &c, const Point<T> &d, Point<double> &O
) {
    if (det(b - a, d - c) == 0) {
        if (det(b - a, c - a) == 0) {
            return -1;
        }
        return 0;
    }
    auto s1 = det(1.0 * d - a, 1.0 * c - a);
    auto s2 = det(1.0 * c - b, 1.0 * d - b);
    O = a + 1.0 * s1 / (s1 + s2) * (b - a);
    return 1;
}
const int M = 1e5 + 10;

Point<long long> P[M], Q[4 * M];
long long a[4 * M];
bool mark[4 * M];
int p[4 * M];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        P[i] = Point(2 * x, 2 * y);
    }
    for (int i = 0; i < n; ++i) {
        Q[2 * i] = P[i];
        Q[2 * i + 1] = (P[i] + P[(i + 1) % n]) / 2;
    }
    for (int i = 0; i < 2 * n; ++i) {
        Q[i + 2 * n] = Q[i];
    }
    for (int i = 0; i < 4 * n; ++i) {
        Point A = Q[(i - 1 + 4 * n) % (4 * n)];
        Point B = Q[(i + 1) % (4 * n)];
        a[i] = i & 1 ? (A / 2 - B / 2).len2() : dot((Q[i] - A) / 2, (Q[i] - B) / 2);
    }
    std::vector<Line<long long>> axis;
    for (int i = 0, l = 0, r = -1; i < 4 * n; ++i) {
        int k = r < i ? 0 : std::min(p[l + r - i], r - i);
        while (0 <= i - k - 1 && i + k + 1 < 4 * n && a[i - k - 1] == a[i + k + 1]) {
            ++k;
        }
        p[i] = k;
        if (r < i + k) {
            l = i - k;
            r = i + k;
        }
        if (p[i] >= n) {
            if (!mark[i] && !mark[i - n]) {
                mark[i] = true;
                mark[i + n] = true;
                axis.emplace_back(Q[i], Q[i + n]);
            }
        }
    }
    if (axis.empty()) {
        puts("0");
    } else if (axis.size() == 1) {
        double ans = 0;
        for (int i = 0; i < n; ++i) {
            auto v = P[i] - P[(i + 1) % n];
            auto u = axis[0].first - axis[0].second;
            auto r1 = point_line_distance(P[i], axis[0].first, axis[0].second);
            auto r2 = point_line_distance(P[(i + 1) % n], axis[0].first, axis[0].second);
            auto h = fabs(dot(v, u)) / u.len();
            // printf("%lf %lf %lf\n", r1, r2, h);
            ans += M_PI * (r1 * r1 + r2 * r2 + r1 * r2) * h / 3;
        }
        printf("%.10lf\n", ans / 16);
    } else {
        Point<double> O;
        int ret = line_line_intersection(
            axis[0].first, axis[0].second, axis[1].first, axis[1].second, O
        );
        // printf("%lf %lf\n", O.x, O.y);
        double r = 0;
        for (int i = 0; i < n; ++i) {
            r = std::max(r, (P[i] - O).len());
        }
        // printf("%lf\n", r);
        printf("%.10lf\n", 4.0 / 3.0 * M_PI * r * r * r / 8);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 14820kb

input:

3
0 -1
1 0
0 1

output:

1.0471975512

result:

ok found '1.0471976', expected '1.0471976', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 14776kb

input:

3
1 1
4 5
1 4

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

score: 0
Accepted
time: 3ms
memory: 15000kb

input:

10
-54592357 -80406461
-54592497 -80409914
-54583785 -80448527
-54573150 -80452302
-54571418 -80445561
-54573057 -80436942
-54574710 -80428961
-54576431 -80421748
-54581146 -80413624
-54586843 -80406612

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

100
19218707 41938436
19227173 41936741
19236439 41934895
19244714 41933329
19263050 41933508
19269952 41935468
19276958 41938057
19283547 41941029
19290649 41944891
19298015 41949938
19301176 41952107
19308530 41957785
19315067 41963572
19323587 41972122
19331125 41980143
19339499 41989094
19341411...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 15388kb

input:

1000
-40710097 -68387840
-40713262 -68382547
-40715876 -68378183
-40720034 -68371279
-40724775 -68363579
-40730740 -68353973
-40736549 -68344830
-40739819 -68339713
-40742687 -68335270
-40746895 -68328767
-40752947 -68319823
-40754886 -68316968
-40761079 -68308110
-40767747 -68298732
-40770472 -6829...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 15424kb

input:

10000
84849929 -57126112
84841472 -57123352
84836897 -57121859
84827816 -57118905
84819535 -57116213
84810908 -57113420
84809250 -57112891
84802608 -57110788
84797710 -57109239
84789766 -57106738
84783187 -57104673
84773775 -57101720
84766522 -57099445
84757149 -57096507
84751370 -57094702
84745393 ...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 5ms
memory: 16304kb

input:

20000
36695920 63855096
36699821 63853995
36702135 63853342
36706473 63852120
36712051 63850550
36717151 63849119
36721923 63847781
36730794 63845294
36739373 63842890
36745062 63841296
36751484 63839501
36760104 63837093
36769910 63834359
36779620 63831652
36788710 63829118
36797797 63826588
368057...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 9ms
memory: 16448kb

input:

50000
63220612 55859143
63226689 55860975
63228549 55861536
63237384 55864204
63246036 55866818
63253128 55868961
63262941 55871927
63272384 55874783
63278109 55876515
63285718 55878817
63289955 55880101
63297340 55882339
63305978 55884958
63313100 55887118
63321418 55889645
63330759 55892485
633335...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #9:

score: 0
Accepted
time: 17ms
memory: 16384kb

input:

100000
6150629 209064536
6145207 209063168
6135217 209060644
6125551 209058201
6115985 209055782
6108484 209053885
6099150 209051524
6093683 209050141
6084620 209047848
6081814 209047138
6072408 209044758
6064213 209042684
6055932 209040588
6047114 209038356
6037530 209035930
6028054 209033531
60199...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #10:

score: 0
Accepted
time: 22ms
memory: 16448kb

input:

99989
-135597084 24675451
-135596066 24669344
-135594745 24661432
-135593849 24656066
-135593366 24653174
-135591982 24644890
-135590618 24636739
-135590005 24633076
-135588796 24625860
-135587482 24618020
-135586605 24612788
-135585381 24605487
-135583879 24596531
-135583397 24593658
-135582102 245...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #11:

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

input:

12432
-53030605 62756639
-53020643 62747841
-53011057 62739377
-53003690 62732873
-52999478 62729161
-52992709 62723198
-52986581 62717802
-52979396 62711476
-52974388 62707069
-52973366 62706172
-52970127 62703330
-52965879 62699603
-52955918 62690870
-52948653 62684509
-52940428 62677331
-52931644...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #12:

score: 0
Accepted
time: 15ms
memory: 16364kb

input:

95846
96281192 -1877350
96286947 -1871034
96291470 -1866068
96300515 -1856135
96306553 -1849500
96315540 -1839624
96320958 -1833670
96328658 -1825206
96336295 -1816811
96341317 -1811290
96348753 -1803115
96355968 -1795181
96360393 -1790315
96366306 -1783812
96372117 -1777421
96375231 -1773996
963804...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #13:

score: 0
Accepted
time: 19ms
memory: 16272kb

input:

77877
134743677 56655124
134749156 56665110
134753149 56672389
134758418 56681995
134761944 56688425
134766712 56697123
134770923 56704806
134775444 56713057
134779077 56719688
134782792 56726469
134788085 56736131
134789440 56738605
134793460 56745946
134798926 56755928
134803171 56763683
134807060...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #14:

score: 0
Accepted
time: 7ms
memory: 16272kb

input:

44722
-1000000000 -1000000000
-999999999 -999999999
-999999998 -999999996
-999999997 -999999991
-999999996 -999999984
-999999995 -999999975
-999999994 -999999964
-999999993 -999999951
-999999992 -999999936
-999999991 -999999919
-999999990 -999999900
-999999989 -999999879
-999999988 -999999856
-99999...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #15:

score: 0
Accepted
time: 4ms
memory: 15132kb

input:

30000
-999999999 -999999999
-999999997 -999999991
-999999995 -999999975
-999999993 -999999951
-999999990 -999999900
-999999989 -999999879
-999999987 -999999831
-999999984 -999999744
-999999983 -999999711
-999999982 -999999676
-999999980 -999999600
-999999979 -999999559
-999999977 -999999471
-9999999...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #16:

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

input:

23333
-1000000000 -1000000000
-999999996 -999999984
-999999994 -999999964
-999999993 -999999951
-999999992 -999999936
-999999991 -999999919
-999999986 -999999804
-999999985 -999999775
-999999983 -999999711
-999999979 -999999559
-999999977 -999999471
-999999976 -999999424
-999999975 -999999375
-99999...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 13332kb

input:

10
-999998304 -997123584
-999995033 -975328911
-999991449 -926880399
-999989625 -892359375
-999986588 -820118256
-999985688 -795166656
-999983492 -727485936
-999982787 -703712631
-999975967 -422414911
-999964606 252735236

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #18:

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

input:

4
0 -1000000000
1 -1
2 999999999
1 0

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #19:

score: -100
Wrong Answer
time: 1ms
memory: 14144kb

input:

12
66207546 277078203
66231235 277049680
66236583 277045669
66270598 277030914
66302758 277017619
66330166 277008238
66376807 277002726
66421946 277004478
66139790 277216095
66150747 277172271
66169098 277129039
66185778 277105354

output:

0

result:

wrong answer 1st numbers differ - expected: '3678257734031382.0000000', found: '0.0000000', error = '1.0000000'