SolarEnergy

You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified N stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of the spaceship that maximizes the distance it can travel.

Space is modeled as a 2D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star i can provide enough energy to travel T_i distance if the spaceship is launched at an angle of a_i with the x-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of a with the x-axis, then it gets enough energy to travel distance of

max(0,T_i−s_i⋅dist(a_i,a))

from star i, where dist(a,b) is the minimum radians needed to go from angle a to b. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance T that the starship can travel.

The first line contains the value N 1≤N≤10⁵. Following this are N lines each containing three real numbers T_i, s_i, and a_i, with 0<T_i≤1000, 0≤s_i≤100, and 0≤a_i<2π. All real numbers in the input have at most 6 digits after the decimal point.

#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); int n; double t, s, a, res, key; int main() { scanf("%d", &n); vector<pair<double, double> >v; for (int i = 0; i < n; i++) { scanf("%lf%lf%lf", &t, &s, &a); res += max(0.0, t - s * min(a, 2 * pi - a)); double x = a - min(pi, t / s), y = a + min(pi, t / s); if (x < 0.0) { key += s; x += 2 * pi; } if (y > 2 * pi) { key -= s; y -= 2 * pi; } v.push_back(make_pair(x, s)); v.push_back(make_pair(a, -2 * s)); v.push_back(make_pair(y, s)); } sort(v.begin(), v.end()); double ans = res, xx = 0.0; for (auto u : v) { res += key * (u.first - xx); xx = u.first; key += u.second; ans = max(ans, res); } printf("%.12lf", ans); }

详情