QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#57950#4838. Rotate Sum 2Sorting#TL 459ms4112kbC++1.5kb2022-10-23 22:44:242022-10-23 22:44:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-23 22:44:26]
  • 评测
  • 测评结果:TL
  • 用时:459ms
  • 内存:4112kb
  • [2022-10-23 22:44:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int N = 1e5 + 3;
const ld PI = acos((ld)-1.0);

int n;
pair<ll, ll> v[N];

ld get_angle(ll x1, ll y1, ll x2, ll y2){
    ld val = x1 * x2 + y1 * y2;
    val /= sqrt((ld)x1 * x1 + y1 * y1) * sqrt((ld)x2 * x2 + y2 * y2);
    return acos(val);
}

ld area(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
    ll a = x1 * y2 + x2 * y3 + x3 * y1
          -(x1 * y3 + x2 * y1 + x3 * y2);
    return ((ld)a) / 2.0;
}

ld cross(pair<ll, ll> p1, pair<ll, ll> p2){
    return p1.first * p2.second - p2.first * p1.second;
}

ld polygonArea(){
    ld a = cross(v[n], v[1]);
    for(int i = 1; i <= n - 1; ++i){
        a += cross(v[i], v[i + 1]);
    }
    return a / 2;
}

ll sq(ll x){
    return x * x;
}

ll d2(pair<ll, ll> p1, pair<ll, ll> p2){
    return sq(p1.first - p2.first) + sq(p1.second - p2.second);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> v[i].first >> v[i].second;
    }
    v[n + 1] = v[1];
    v[0] = v[n];

    ld ans = 0;
    for(int i = 1; i <= n; ++i){
        ld angle = get_angle(v[i].first - v[i - 1].first, v[i].second - v[i - 1].second, v[i].first - v[i + 1].first, v[i].second - v[i + 1].second);
        for(int j = 1; j <= n; ++j)
            ans += (PI - angle) * d2(v[i], v[j]) / 2;
    }
    ans /= n;
    cout << fixed << setprecision(12) <<  ans + polygonArea() << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3768kb

input:

3
1 -1
1 1
-1 2

output:

18.763234503174

result:

ok found '18.76323', expected '18.76323', error '0.00000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3724kb

input:

4
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
1000000000 1000000000

output:

16566370614359172954.000000000000

result:

ok found '16566370614359173120.00000', expected '16566370614359173120.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3736kb

input:

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

output:

3241469216.962166742887

result:

ok found '3241469216.96217', expected '3241469216.96217', error '0.00000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3768kb

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:

168840266155.043103665113

result:

ok found '168840266155.04309', expected '168840266155.04294', error '0.00000'

Test #5:

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

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:

14911692181599.201914787292

result:

ok found '14911692181599.20117', expected '14911692181599.02734', error '0.00000'

Test #6:

score: 0
Accepted
time: 119ms
memory: 3884kb

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:

1412486655950571.326782226562

result:

ok found '1412486655950571.25000', expected '1412486655950472.75000', error '0.00000'

Test #7:

score: 0
Accepted
time: 459ms
memory: 4112kb

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:

5727102515432339.189453125000

result:

ok found '5727102515432339.00000', expected '5727102515430790.00000', error '0.00000'

Test #8:

score: -100
Time Limit Exceeded

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:


result: