HDU 1006 Tick and Tick （happy模拟）

HDU1006 Tick and Tick

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

題目大意：

找到一天時針分針秒針三者所産生的三個夾角均大于所給角D的百分比。

題目中秒針可以看做是劃過，時針分針每時每刻都在跟着運動，是以是不能将最小機關設成秒或度來計算。（一開始将秒無限細分來比較，逾時比較嚴重）

解題思路：

首先一天24小時分成兩個12小時，然後将其分成12*60分鐘，計算每分鐘裡的happytime。而計算happytime需要解方程，這樣無精度問題。

時針	分針	秒針
每秒角速度	1/120	1/10	6
一度所用時間	120	10	1/6

周遊12小時*60分鐘，設目前時間走了s秒（s取值範圍為[0,60]）。例如6時40分s秒，此時周遊小時數h和分鐘數m都是已知數。

計算目前每個指針的角度，這三個公式可以自己手推一遍。

hh=30*h+m/2+s/120;

mm=6*m+s/10;

ss=6*s;

例如：hh時針走過角度=時針*360度/12小時+分針*360度/60分鐘/12小時+秒針*360度/60秒/60分鐘/12小時。

然後計算三個不等式和區間[0,60]交集。

D<=|hw-mw|<=360-D

D<=|hw-sw|<=360-D

D<=|mw-sw|<=360-D

上面給出公式hh、mm、ss=xxxx代入絕對值不等式隻含一個未知數秒s，轉化為

D<=|ax+b|<=360-D

的問題，x為秒s。

求出三個區間，與[0,60]求交集，得出h和m，h和s，m和s的三個兩兩指針的happy區間，将這三個區間求交集就為這一分鐘的happy區間。

思路要清晰，解題前最好在紙上推好公式。

代碼如下：

#include <bits/stdc++.h>
using namespace std;

struct qujian{
    double l,r;
};

double D;

qujian jiao(qujian a,qujian b){
    qujian p;
    p.l=max(a.l,b.l);
    p.r=min(a.r,b.r);
    if (p.l>=p.r) p.l=p.r=0;
    return p;
}

qujian solve(double a,double b){
    qujian p;
    ///D<=|ax+b|<=360-D;
    if (a>0){
        p.l=(D-b)/a;
        p.r=(360-D-b)/a;
    }
    else {
        p.l=(360-D-b)/a;
        p.r=(D-b)/a;
    }
    if (p.l<0) p.l=0;
    if (p.r>60) p.r=60;
    if (p.l>=p.r) p.l=p.r=0;
    return p;
}

double happytime(double h,double m){
    double a,b;
    qujian s[3][2];
    qujian ss;
    ///D<=|hw-mw|<=360-D;
    ///D<=|hw-sw|<=360-D;
    ///D<=|mw-sw|<=360-D;
    ///[0,60]

    ///hh=30*h+m/2+s/120;
    ///mm=6*m+s/10;
    ///ss=6*s;
    /// |xx-xx|=a*x+b

    ///D<=|hw-mw|<=360-D;
    a=1.0/120-1.0/10;
    b=30*h+m/2-6*m;
    s[0][0]=solve(a,b);
    s[0][1]=solve(-a,-b);

    ///D<=|hw-sw|<=360-D;
    a=1.0/120-6;
    b=30*h+m/2;
    s[1][0]=solve(a,b);
    s[1][1]=solve(-a,-b);

    ///D<=|mw-sw|<=360-D;
    a=1.0/10-6;
    b=6*m;
    s[2][0]=solve(a,b);
    s[2][1]=solve(-a,-b);


    double res=0;
    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            for (int k=0; k<2; k++){
                ss = jiao( jiao(s[0][i],s[1][j]) , s[2][k] );
                res=res+ss.r-ss.l;
            }
        }
    }

    return res;
}

int main() {
    double h,m,s,sum;
    while (~scanf("%lf",&D) && D!=-1){
        sum=0;
        for (int i=0; i<12; i++){
            for (int j=0; j<60; j++){
                h=i; m=j;
                sum=sum+happytime(h,m);
            }
        }

        sum = sum*100.0 / (12*60*60);
        printf("%.3f\n",sum);
    }
    return 0;
}

           

開始時不會做，參考大神部落格後做的題，并寫此題解（侵删）。

果凍0_0 https://www.cnblogs.com/huangguodong/p/5553939.html

kuangbin的部落格園https://www.cnblogs.com/kuangbin/archive/2011/12/04/2275470.html