学步园

1006这个题难点在需要达到非常高的精度，即要求秒针不是一秒走一下，而且三根针都在不断的走。于是最容易想到的穷举所有秒来判断是否符合happy time的方法就行不通了。例如当输入为90的时候，采用穷举每一秒的结果是6.255，和示例的5.251差了比较大的精度。网上参考了很多的方法，采取了一个公式法来计算每一分钟中符合条件的秒数。于是我们只需要循环12小时*60分钟=720次，再每次循环中用公式法计算出符合条件的秒数（double型），再累计依赖除以总秒数就可以了。

做法主要参考这个帖子：http://hi.baidu.com/guoxiangke2008/blog/item/72c59bd5e51841cc51da4bd4.html

算法的难点主要是数学公式的推导和交并集的处理。

以下引用自上述的帖子：

设当前的时间为 H:M:S, 其中 0 <= H < 12, 0 <= M < 60, 0 <= S < 60, H,M皆为整数, S为实数
于是时针、分针、秒针相对于时刻 0:0:0 的转角分别为
 A(H) = 30H + M/2 + S/120;
 A(M) = 6M + S/10;
 A(S) = 6S;
 设题目中的临界夹角为 D,则“快乐时光”是同时满足以下不等式的解:
 D <= | A(H) - A(M) | <= 360-D;   (1)

 D <= | A(H) - A(S) | <= 360-D;   (2)

 D <= | A(M) - A(S) | <= 360-D;   (3)
 上面各式的绝对值中的形式为 bS - a,(a,b为常数,b>0) 故解的形式为
 [ (a+D)/b, (a+360-D)/b) ] 并 [ (a+D-360)/b, (a-D)/b ], 即两个闭区间的并集.
 设由式(i)得到的解集为 Si1 并 Si2, 那么“快乐时光”在时、分确定的情况下，其秒的解集为
 [0,60] 交 (S11 并 S12) 交 (S21 并 S22) 交 (S31 并 S32)
 上面的集合容易化成 S1 并 S2 并 S3 并 S4 并 S5 并 S6 并 S7 并 S8 的形式,其中 S1,S2,...皆为闭区间.
 求区间的并的总长度没有困难,而这个总长度就是由时、分确定的“快乐时光”的长度

代码如下：

#include <iostream>
#include <cmath>
#include <iomanip> 

using namespace std;

struct Segment{ double a,b;};
double d;


Segment makeseg1(double a, double b);
Segment makeseg2(double a, double b);
Segment operator *(Segment S1,Segment S2){
        Segment seg;
        seg.a = max(S1.a,S2.a);
        seg.b = min(S1.b,S2.b);
        if( seg.a >= seg.b )
                seg.a = seg.b = 0.0;
        return seg;
}

int main()
{
    while(cin>>d)
    {
        if(d<0) break;
        double totlen=0.0;
        for(int h=0;h<12;h++)
        {
            for(int m=0;m<60;m++)
            {
                Segment s[3][2];
                double a,b;
                a=30.0*h - 5.5*m;    b=11.0/120;
                s[0][0]=makeseg1(a,b);            s[0][1]=makeseg2(a,b);
                a=30.0*h + 0.5*m;    b=719.0/120.0;
                s[1][0]=makeseg1(a,b);            s[1][1]=makeseg2(a,b);
                a=6.0*m;              b=5.9;
                s[2][0]=makeseg1(a,b);            s[2][1]=makeseg2(a,b);
                for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                {
                Segment tmp=s[0][i]*s[1][j]*s[2][k];
                totlen+=tmp.b-tmp.a;
                }
            }
        }
        cout<<setprecision(3)<<setiosflags(ios::fixed);
        cout<<totlen/432.0<<endl;
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

Segment makeseg1(double a, double b)
{
    Segment seg;
    seg.a=(a+d-360.0)/b;
    seg.b=(a-d)/b;
    if (seg.a<0.0) seg.a=0.0;
    if (seg.b>60.0) seg.b=60.0;
    if(seg.a>seg.b) seg.a=seg.b=0.0;
    return seg;
}

Segment makeseg2(double a, double b)
{
    Segment seg;
    seg.a=(a+d)/b;
    seg.b=(a-d+360.0)/b;
    if (seg.a<0.0) seg.a=0.0;
    if (seg.b>60.0) seg.b=60.0;
    if(seg.a>seg.b) seg.a=seg.b=0.0;
    return seg;
}