QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#57950 | #4838. Rotate Sum 2 | Sorting# | TL | 459ms | 4112kb | C++ | 1.5kb | 2022-10-23 22:44:24 | 2022-10-23 22:44:26 |
Judging History
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";
}
Details
Tip: Click on the bar to expand more detailed information
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...