杭电1006

Problem Description

The three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.

Input

The input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.

Output

For each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.

Sample Input

120

90

-1

Sample Output

100.000

0.000

6.251

我开始就误解了，第一句说了rotating every second，有很多钟的秒针是一秒跳一次，中间有间隔的。我自然而然地想着按秒来算。由于一天之内是两个循环，分别是0：00~11：59，以及12：00~23：59.这两个循环过程中，时分秒针的轨迹一模一样，所以只用考虑第一个就好了。按秒算的思路是：时分秒三重循环，对每一秒进行判断，若符合角度要求，就让计数器加一。由于12个小时之内总共又43200秒，一除，就可得到happy time的比例。

这样写不能说不对，但是不符合本题要求。题目默认的是那种秒针一直匀速转动。于是存在情况：符合跟不符合要求的分界（boundary）有可能不是整数秒，所以逐秒判断的方法就产生了很大误差。

换另外一种思路，遍历12个小时里的每一分钟，把每分钟内符合要求的秒数区间算出来，这个区间的上下界可以是小数。二重循环，外循环是12个小时，内循环是每个小时里的60分钟。一圈360°，12个小时是一圈，故一个小时的圆心角是30°，同理，一分钟6°，一秒钟6°。注意：分针会受到秒针的转动的影响，而时针会受到分针和秒针转动的影响。每过一秒钟，意味着1/60分钟过去，分针就被带动6*1/60，即0.1°；每过一分钟，就意味着1/60小时过去，时针就被带动30*1/60，即0.5°；每过一秒钟，就意味着1/3600小时过去，时针就被带动30*1/3600，即1/120°。

因此在hour：minute：x（0<=x<60）时刻，时针相对0的圆心角是hour*30+minute*0.5+x*1/120，分针相对0的圆心角是minute*6+x*0.1，秒针相对0的圆心角是x*6。根据要求，要各针两两之间形成的角度大于等于D。将二者的相对圆心角的表达式一减，再取一个绝对值，得θ，这个θ就可以表示较小相对角度的针顺时针方向到较大相对角度的针形成的角度。反方向获得的角度就是360°-θ。我们要保证二者都要大于等于D。整理不等式，可知θ应该在[D,360°-D]之间。以秒针与分针之间为例，有:

D<=|6*x - （0.1*x+minute*6）|<=360-D。

x的解区间为[(D+6*minute)/5.9,(360-D+6*minute)/5.9]U[(D+6*minute-360)/5.9,(6*minute-D)/5.9].再考虑到x肯定在0到60之间，需要对越界的情况进行调整，所以发现了解区间的边界小于零则置为零，大于60则置为60。类似的，秒针与时针，分针与时针都可以获得两个并在一起的解区间，因为两两之间都要满足这个角度要求，所以最后获得的解应该是三个解区间的交集：

(aUb)∩(cUd)∩(e∪f),化为：

(a∩c∩e)∪(b∩e∩c)∪(a∩e∩d)∪(b∩e∩d)∪(a∩f∩c)∪(b∩f∩c)∪(a∩f∩d)∪(b∩f∩d)

很直观地理解为：每个解区间里的两个子集中任选一个出来进行组合，共有2^3，即八种，对应八个交集。怎么求求交集呢？选择最大的下界跟最小的上界就好了。

之后就是求并集。要知道：|f(x)|大于y1，小于y2的解是不存在公共区域的。由于在本题中的f(x)均是一次线性函数，所以反函数也是一次线性的，于是最后得出x的区间也是没有公共区域的，故a跟b，c跟d，e跟f都是没有公共区域的，因此上述的几个交集之间，没有公共区域。所以它们的并集，就是简单的相加。

最后注意题目说D是实数，我刚开始用float输入，不通过，要用double才行。

#include <stdio.h>

int main()
{
    double D,lower,upper;
    double boundary[];
    double seconds_count,rate_percent;
    int hour,minute,second;

    while(scanf("%lf",&D)!=EOF)
    {
        if(D==-)
            break;
        seconds_count = ;
        hour = minute = second = ;
        for(hour=;hour<;)//对12小时内的每一分钟进行处理
        {
            for(minute=;minute<;)
            {
                boundary[] = (D+*minute)/;//秒针时针之间的子集1的下界
                boundary[] = (-D+*minute)/;//秒针时针之间的子集1的上界
                boundary[] = *(D+*hour+*minute)/;
                boundary[] = *(-D+*hour+*minute)/;
                boundary[] = *(D+*hour-*minute)/;
                boundary[] = *(-D+*hour-*minute)/;

                boundary[] = (D+*minute-)/;//秒针时针之间的子集2的下界
                boundary[] = (*minute-D)/;//秒针时针之间的子集2的上界
                boundary[] = *(D+*hour-+*minute)/;
                boundary[] = *(*hour+*minute-D)/;
                boundary[] = *(D-+*hour-*minute)/;
                boundary[] = *(*hour-*minute-D)/;

                for(int p=;p<;)//越界处理
                {
                    if(boundary[p]<)
                        boundary[p] = ;
                    if(boundary[p]>)
                        boundary[p] =;
                    if(boundary[p+]<)
                        boundary[p+] = ;
                    if(boundary[p+]>)
                        boundary[p+] = ;
                    p += ;
                }
                for(int i=;i<;i++)//三种情况下的子集选取组合
                {
                    for(int j=;j<;j++)
                    {
                        for(int k=;k<;k++)
                        {
                            lower = boundary[+*i];//最大下界
                            if(boundary[+*j]>lower)
                                lower = boundary[+*j];
                            if(boundary[+*k]>lower)
                                lower = boundary[+*k];

                            upper = boundary[+*i];//最小上界
                            if(boundary[+*j]<upper)
                                upper = boundary[+*j];
                            if(boundary[+*k]<upper)
                                upper = boundary[+*k];

                            if(lower<upper)
                                seconds_count = seconds_count + upper -lower;//加入并集之中
                        }
                    }
                }
                minute++;
            }
            hour++;
        }
        rate_percent = seconds_count/;//其实是除以43200，再乘以100，来求得百分比
        printf("%.3lf\n",rate_percent);
    }
    return ;
}