QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139616#5727. Interstellar TravelNicolas125841WA 1ms3724kbC++172.1kb2023-08-14 03:59:152023-08-14 03:59:19

Judging History

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

  • [2023-08-14 03:59:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2023-08-14 03:59:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long 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(13) << md << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3724kb

input:

2
100 1 1
100 1 1.5

output:

-nan

result:

wrong output format Expected double, but "-nan" found