杭電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 ;
}