题意：给出一个轮子，上面有一个随着它转动的传感器在圆周上，给出一个指定距离m，和轮子向前行进的速度v以及轮子的半径r。问让传感器通过该距离最少需要多少时间。
分析：首先我们列出传感器行进距离与时间的轮子行进距离的关系：f(c) = c+r*sin(c/r)。其中c是距离，r是半径。该公式表示传感器从轮子正上方开始运行索性进的距离。
我们可以先去除一种情况，就是距离m是直径2r的整数倍，那么传感器在开始点和结束点所处的角度是相同的，无论从哪个角度开始所需的时间都是一样的。
我们只考虑非整数倍的情况。
要看传感器行进速度的变化，我们需要对这个函数f关于c进行求导。
求得导数是：f'(c) = 1+cos(c/r)。这就是传感器速度的函数。而这个函数图像与x轴所夹的面积就是行进距离。
那么，我们现在的任务就变成了在这个图像上截取一段，使得与x轴所夹的面积是m，且要保证我们截取的横向长度最短。（因为速度是一定的，距离和时间成正比）
假设我们截取了x=a到x=b。那么一定有f'(a)=f'(b)。如果两者不等，例如f'(a)<f'(b)，我只要将右边缘向右平移一点点，保证面积不变的话，就需要将左边缘向右平移更多。
因为我们如果把这个增量看成小长方体，如果左右平移量相等，f'(a)<f'(b)导致右边进来的就比左边进来的长方体高，那面积就变了。
既然f'(a)=f'(b)，就一定a在图像的递增区域，b在递减区域，否则还会出现上面的情况，或者就是m是2r的整数倍。
也就是说两边缘必须对称，也就是说选区的中间是最高点或者最低点。我们只需要对两种情况分别进行二分查找即可。
二分查找的时候查找轮子的行进长度，每次观察f(c)>=m/2是否成立。
二分查找有个需要特别注意的地方。如果每次只是限定L和R的差值是不行的。差值设大了就会出现WA，设小了会TLE。
需要限定二分迭代的次数为50次左右。不知道是不是其他的比赛或者OJ也有这种情况。
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define d(x) #define zero(x) (((x)>0?(x):-(x))<eps) #define eps 1.0E-8 int double_cmp(double a) { if (zero(a)) return 0; return a > 0 ? 1 : -1; } int n, radius, v; int dist; bool top_ok(double bike_dist) { double ret = bike_dist + radius * sin(bike_dist / radius); return double_cmp(ret * 2.0 - dist) >= 0; } bool bottom_ok(double bike_dist) { double ret = bike_dist - radius * sin(bike_dist / radius); return double_cmp(ret * 2.0 - dist) >= 0; } double binary_search(bool (*ok)(double)) { double l = max(0.0, dist / 2.0 - 2 * radius); double r = dist / 2.0 + 2 * radius; int cnt = 0; while (double_cmp(r - l) > 0) { double mid = (l + r) / 2; if (ok(mid)) r = mid; else l = mid; cnt++; if (cnt > 100) break; } d(printf("%.2f ", l / radius / 2 / 3.14)); return l; } double work() { double time_top = binary_search(&top_ok) / v; double time_bottom = binary_search(&bottom_ok) / v; d(printf("%.2f %.2f ", time_top, time_bottom)); return min(time_top, time_bottom) * 2; } int main() { scanf("%d", &n); scanf("%d%d", &radius, &v); for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); dist = b - a; printf("%.12f ", work()); } return 0; }