hdu1006(几何 + 枚举)

原创： http://blog.csdn.net/a601025382s/article/details/37814777

这题我曾多次拿起，又多次放下，一直觉得好难，有些数字及公式完全不知道是如何得来的。这次终于坚持下来了，将其看懂了，写个博客留恋下。(^__) 嘻嘻……

题意： 时针，分针和秒针都厌倦了其余两针，只有在与其余两针保持n度以上的距离才能感到高兴。问一天中，三针都高兴的时间占总时间的百分比。注意时间是连续的。

输入(n)： (0 <= n <= 120)

0
120
90
-1

输出(百分比)： （以-1结束输入）

100.000
0.000
6.251

贴个钟：

先普及些知识：
一个以弧度为单位的圆（一个圆周为2π，即：360度=2π)，在单位时间内所走的弧度即为角速度。在国际单位制中，单位是“弧度/秒”（rad/s）。（1rad = 360°/(2π) ≈ 57°17'45″）。周期T和频率f的关系是：T=1/f。比如说周期是0.2秒，说明一秒转5圈，故频率是5。转速：做圆周运动的物体单位时间内沿圆周绕圆心转过的圈数，叫做转速，单位为r/s（转/秒）或r/min（转/分），当单位为r/s时，在数值上转速n与频率f相等。

• v（线速度） = ΔS / Δt = 2πr / T = ωr = 2πrf (S代表弧长，t代表时间，r代表半径,f代表频率)
• ω（角速度） = Δθ / Δt = 2π / T = 2πn （θ表示角度或者弧度）
• T（周期） = 2πr / v = 2π / ω
• n（转速） = 1 / T = v / 2πr = ω / 2π

思路：先缩短一半的时间：早上的12个小时和下午的12小时对时钟是一样的，因为时钟12小时与0小时的三针位置相同。接着就是了解到每次所有的针从有重合到再次有重合至多有一段连续的段符合三针分离度大于n。所以只要枚举每个重合到重合的时间段，然后求出每段中符合条件的时间段即可。
由于枚举的是重合到重合，所以先求出时针和分针，分针和秒针，时针和秒针之间的相对角速度和再重合周期。通过相对角速度W_hm，W_hs，W_ms，我们可以求出从重合到分离n度所需的时间n / W_hm，n / W_hs，n / W_ms，以及到再重合前n度所需的时间(360 - n) / W_hm，(360 - n) / W_hs，(360 - n) / W_ms。每次枚举，hm，hs，ms表示W_hm，W_hs，W_ms各自重合的时间，那么res1 = max(hm + n / W_hm, hs + n / W_hs, ms + n / W_ms)就是最早的三针分离n度的时间；res2 = min(hm + (360 - n) / W_hm, hs + (360 - n) / W_hs, ms + (360 - n) / W_ms)就是最晚三针合并到n度的时间，那么时间区间[res1, res2]就是符合条件的时间段。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;

#define PI 3.14159265
#define e 2.71828182

typedef long long ll;
typedef pair<double, double> P;
const ll MAX_N = 1 << 17;

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);
    
    //秒针每秒转6度，分针60秒转6度（一分钟），时针3600秒转30度（一个小时）。
    double W_s = 6, W_m = 1.0 / 10.0, W_h = 1.0 / 120.0;//角速度

    //两指针的相对角速度，即分离的速度（相当于物理中的追及问题）
    double W_hs = W_s - W_h;
    double W_hm = W_m - W_h;
    double W_ms = W_s - W_m;
    
    //两针从重合到再次重合所花的时间。（角速度公式）
    double T_hs = 360.0 / W_hs;
    double T_hm = 360.0 / W_hm;
    double T_ms = 360.0 / W_ms;

    double N = 12.0 * 60.0 * 60.0;//一天的时间，单位为秒

    double n;//输入的度数
    while (scanf("%lf", &n) && n >= 0.0) {
        double ans = 0.0;//表示12*60*60秒中有多少秒符合条件

        //两针分离到n度所需要的时间
        double n_hs1 = n / W_hs;
        double n_hm1 = n / W_hm;
        double n_ms1 = n / W_ms;
        
        //两针合并到n度时所需要的时间（还差n度就再次重合）
        double n_hs2 = (360.0 - n) / W_hs;
        double n_hm2 = (360.0 - n) / W_hm;
        double n_ms2 = (360.0 - n) / W_ms;
        
        //每次所有的针从有重合到再次有重合至多有一段连续的段符合三针分离度大于n。
        for (double hs = 0.0; hs <= N; hs += T_hs) {
            for (double hm = 0.0; hm <= N; hm += T_hm) {
                
                //表示两者没有交集
                if (hm + n_hm2 < hs + n_hs1) continue;//因为hm会随着循环增大
                if (hs + n_hs2 < hm + n_hm1) break;//hs在这个循环中不变，而hm一直在增大，所以break

                for (double ms = 0.0; ms <= N; ms += T_ms) {
                    //同上
                    if (ms + n_ms2 < hs + n_hs1 || ms + n_ms2 < hm + n_hm1) continue;
                    if (hm + n_hm2 < ms + n_ms1 || hs + n_hs2 < ms + n_ms1) break;
                    
                    //在这三个时间段刚好完成分离n度，所以取最大值才能保证全都分离n度以上  
                    double res1 = max(max(hs + n_hs1, hm + n_hm1), ms + n_ms1);
                    //在这三个时间段刚好完成合并n度，所以取最小值才能保证全都未合并到n度以内
                    double res2 = min(min(hs + n_hs2, hm + n_hm2), ms + n_ms2);

                    //相当于取res1对应图与res2对应图的交集，只有交集部分才大于n度
                    if (res1 < res2) ans += res2 - res1;
                }
            }
        }
        printf("%.3lf\n", ans / N * 100.0);//所占比例的百分比
    }
    return 0;
}