QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139617#5727. Interstellar TravelNicolas125841AC ✓210ms30560kbC++172.1kb2023-08-14 04:02:262023-08-14 04:02:29

Judging History

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

  • [2023-08-14 04:02:29]
  • 评测
  • 测评结果:AC
  • 用时:210ms
  • 内存:30560kb
  • [2023-08-14 04:02:26]
  • 提交

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'