题解 accoders::NOI 5510【飞翔的胖鸟（fly）】
problem
求 \(f(x)=\frac{ah}{\sin(x)}+bx\) 在 \((0,\frac\pi 2]\) 上的最小值。
solution
\(\sin'(x)=cos(x); \cos'(x)=-\sin(x)\)。
\((f(x)\cdot g(x))'=f'(x)g(x)+f(x)g'(x)\)。
\(\left(\dfrac{f(x)}{g(x)}\right)'=\dfrac{f'(x)g(x)-f(x)g'(x)}{g^2(x)}.\)
\(f'(x)=ah\frac{\cos(x)}{\sin^2(x)}+b=ah\frac{\cos(x)}{1-\cos^2(x)}+b\)。
因为在 \((0,\frac\pi 2]\) 上导数单调递增，故当导数 \(f'(x)=0\) 时原函数取到最小值，即以 \(\cos(x)\) 为未知数解一元二次方程
\[ah\frac{\cos(x)}{1-\cos^2(x)}+b=0 \implies ah\cos(x)+b(1-\cos^2(x))=0
\]
直接牛顿迭代 \(x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}\) 可以获得 TLE 的好成绩，因为询问数太多。
code
// ubsan: undefined
// accoders
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const double pi = acos(-1);
double decsolve(double h, double a, double b) {
if (!b)
return a * h;
double delta = a * a * h * h + 4 * b * b;
double y = (-a * h + sqrt(delta)) / 2 / b;
double x = acos(y);
debug("decsolve(%.0lf, %.0lf, %.0lf) = f(%.4lf)\n", h, a, b, x);
return a * h / sin(x) + b * x;
}
int h, a, b, H, A, B, T, typ;
void Read() {
long long x = 1ll * h * H, y = 1ll * a * A, z = 1ll * b * B;
h = (H ^ (y + z)) % 1000 + 1;
a = (A ^ (x + z)) % 1000 + 1;
b = (B ^ (x + y)) % 100000 + 1;
}
int main() {
#ifndef nfio
freopen("fly.in", "r", stdin);
freopen("fly.out", "w", stdout);
#endif
scanf("%d%d", &typ, &T);
if (typ == 0) {
while (T--) {
scanf("%d%d%d", &h, &a, &b);
printf("%.4lf\n", decsolve(h, a, b));
}
} else {
scanf("%d%d%d%d%d%d", &h, &a, &b, &H, &A, &B);
long long ans = 0, mod = 19260817, now = 1;
while (T--) {
Read();
// debug("h = %d, a = %d, b = %d, ans = %.4lf\n", h, a, b, solve(h, a, b));
now = now * 11514 % mod;
ans = (ans + (long long)(decsolve(h, a, b) * 1e4) % mod * now) % mod;
}
printf("%lld\n", ans);
}
return 0;
}