QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139617 | #5727. Interstellar Travel | Nicolas125841 | AC ✓ | 210ms | 30560kb | C++17 | 2.1kb | 2023-08-14 04:02:26 | 2023-08-14 04:02:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
const ld PI = acos(-1.0);
const ld PI2 = PI * (ld)2.0;
int main(){
cin.tie(NULL)->sync_with_stdio(false);
int n;
cin >> n;
//radial sweep line
map<ld, vector<pair<int, ld>>> points;
vector<tuple<ld, ld, ld>> stars;
for(int i = 0; i < n; i++){
ld T, s, a;
cin >> T >> s >> a;
stars.emplace_back(T, s, a);
points[a].emplace_back(i, -s);
if(T - s * PI < (ld)0.0){
ld g_dist = T / s;
if(a + g_dist >= PI2){
points[a + g_dist - PI2].emplace_back(i, 0);
}else{
points[a + g_dist].emplace_back(i, 0);
}
if(a - g_dist < 0){
points[a - g_dist + PI2].emplace_back(i, s);
}else{
points[a - g_dist].emplace_back(i, s);
}
}else{
if(a + PI >= PI2){
points[a - PI].emplace_back(i, s);
}else{
points[a + PI].emplace_back(i, s);
}
}
}
ld dist = 0.0, fp = points.begin()->first, pp, md, ss;
vector<ld> slopes(n);
for(auto &pt : points)
for(auto &st : pt.second)
slopes[st.first] = st.second;
for(const ld &slope : slopes)
ss += slope;
for(int i = 0; i < n; i++)
dist += max((ld)0.0, get<0>(stars[i]) - get<1>(stars[i]) * min(abs(get<2>(stars[i]) - fp), PI2 - abs(get<2>(stars[i]) - fp)));
md = dist;
pp = fp;
auto it = points.begin();
for(const auto &st : it->second){
ss -= slopes[st.first];
slopes[st.first] = st.second;
ss += slopes[st.first];
}
it++;
for(; it != points.end(); it++){
fp = it->first;
dist += ss * (fp - pp);
md = max(md, dist);
for(const auto &st : it->second){
ss -= slopes[st.first];
slopes[st.first] = st.second;
ss += slopes[st.first];
}
pp = fp;
}
cout << fixed << setprecision(6) << md << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
input:
2 100 1 1 100 1 1.5
output:
199.500000
result:
ok found '199.5000000', expected '199.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 100 1 0.5 200 1 1 100 0.5 1.5 10 2 3
output:
405.500000
result:
ok found '405.5000000', expected '405.5000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 103ms
memory: 20520kb
input:
65156 589.879800 23.439587 4.669064 111.188574 61.405781 2.251292 402.539682 35.961327 5.047919 601.440363 52.968892 0.300876 929.328609 40.023141 0.965123 247.579029 55.643707 0.899498 336.117533 26.765365 4.825658 655.889160 86.847477 5.667617 606.234124 51.362894 2.955658 46.788799 79.573087 0.20...
output:
27867620.660152
result:
ok found '27867620.6601520', expected '27867620.6601520', error '0.0000000'
Test #4:
score: 0
Accepted
time: 33ms
memory: 8904kb
input:
20780 457.480798 65.415296 3.651446 631.717164 62.392524 5.905843 531.411231 62.477661 3.272282 455.717524 15.952200 1.548807 753.667209 18.563137 1.581605 213.788373 47.220244 2.187795 360.476724 57.906581 4.411827 747.989057 64.364770 0.275147 454.189139 4.482583 1.445919 448.459992 67.034463 2.00...
output:
8902961.151507
result:
ok found '8902961.1515070', expected '8902961.1515070', error '0.0000000'
Test #5:
score: 0
Accepted
time: 94ms
memory: 17996kb
input:
54794 928.046627 11.834519 2.855723 944.218147 28.206307 5.594957 562.397310 16.314877 5.985967 874.803617 54.143637 5.772357 802.992342 45.062902 6.184437 999.371277 96.803367 1.910329 716.765939 24.372757 5.394717 441.262096 86.310555 0.382004 202.463202 16.937411 3.718756 808.617088 35.640098 4.9...
output:
23310686.538263
result:
ok found '23310686.5382630', expected '23310686.5382640', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
103 100.000000 100.000000 0.000000 99.500000 100.000000 0.061002 99.500000 100.000000 0.122003 99.500000 100.000000 0.183005 99.500000 100.000000 0.244007 99.500000 100.000000 0.305009 99.500000 100.000000 0.366010 99.500000 100.000000 0.427012 99.500000 100.000000 0.488014 99.500000 100.000000 0.54...
output:
1624.752400
result:
ok found '1624.7524000', expected '1624.7524000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
107 99.500000 100.000000 0.000000 99.500000 100.000000 0.058721 99.500000 100.000000 0.117443 99.500000 100.000000 0.176164 99.500000 100.000000 0.234885 99.500000 100.000000 0.293607 99.500000 100.000000 0.352328 99.500000 100.000000 0.411049 99.500000 100.000000 0.469770 99.500000 100.000000 0.528...
output:
1686.780500
result:
ok found '1686.7805000', expected '1686.7805000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
2 100 100 0 99.5 100 3.14159
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
2 100 100 1 99 100 4.14159
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
2 99 100 1 100 100 4.14159
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
4 100 80 0 99.5 80 3.14159 99.5 80 1.570795 99.5 80 4.712385
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
4 100 80 0.5 99.5 80 3.64159 99.5 80 2.070795 99.5 80 5.212385
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
4 99.5 80 0.5 99.5 80 3.64159 100 80 2.070795 99.5 80 5.212385
output:
100.000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 210ms
memory: 28848kb
input:
100000 218.637983 100.000000 4.021337 701.324977 83.903964 0.554289 6.498770 100.000000 5.602484 957.213073 67.318909 0.153934 343.955729 52.904173 4.026135 973.115764 75.706875 2.641459 885.451749 72.327005 1.406152 227.898283 57.877593 0.153385 834.110428 32.530819 4.245030 936.654588 100.000000 0...
output:
41232647.651865
result:
ok found '41232647.6518650', expected '41232647.6518660', error '0.0000000'
Test #15:
score: 0
Accepted
time: 195ms
memory: 30560kb
input:
100000 218.637983 100.000000 4.054635 701.324977 83.903964 0.626611 6.498770 100.000000 5.573279 957.213073 67.318909 0.125013 343.955729 52.904173 4.102617 973.115764 75.706875 2.555470 885.451749 72.327005 1.439255 227.898283 57.877593 0.119524 834.110428 32.530819 4.183843 936.654588 100.000000 0...
output:
41137197.175812
result:
ok found '41137197.1758120', expected '41137197.1758120', error '0.0000000'
Test #16:
score: 0
Accepted
time: 195ms
memory: 27992kb
input:
100000 25.010765 27.502932 4.108451 590.492517 3.178268 3.920055 26.535979 19.883765 3.900873 809.430459 0.649876 4.069159 155.479508 95.721307 3.907582 358.979387 34.395572 4.212587 536.228096 97.311576 3.915408 628.639803 88.545175 4.062555 45.824393 22.789828 4.119063 453.410308 83.411043 3.98946...
output:
49698713.508816
result:
ok found '49698713.5088160', expected '49698713.5088170', error '0.0000000'