首页 > ACM题库 > HDU-杭电 > HDU 1006 Tick and Tick-概率-[解题报告] C++
2013
11-26

HDU 1006 Tick and Tick-概率-[解题报告] C++

Tick and Tick

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

0
120
90
-1

样例输出:

100.000
0.000
6.251

题意:给出一个角度,然后求一天中时针、分针、秒针互相的夹角都大于等于这个夹角的概率。。

思路:开始的思路就是枚举,但是由于精度问题,果断TLE、、、 

膜拜网上各种解法啊,主要就是个数学问题、、但是真心不会啊,这道题学到一些,处理时钟问题的方法吧,还有区间求交集什么的。。。

http://blog.csdn.net/lulipeng_cpp/article/details/7320710 Orz

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline double Max(double a , double b , double c) {
    double tmp = a > b ? a : b;
    tmp = tmp > c ? tmp : c;
    return tmp;    
}
inline double Min(double a , double b , double c) {
    double tmp = a < b ? a : b;
    tmp = tmp < c ? tmp : c;
    return tmp;    
}
int main() {
    double ss , mm , hh , sm , mh , sh , t_sm , t_mh , t_sh;
    ss = 6.0 , mm = 0.1 , hh = 0.1/12.0;
    sm = 6.0 - 0.1;
    mh = 0.1 - 0.1/12.0;
    sh = 6.0 - 0.1/12.0;//相对速度 
    t_sm = 360.0/sm;
    t_mh = 360.0/mh;
    t_sh = 360.0/sh;//相对周期
    int D;
    double m[3] , n[3] , x[3] , y[3];
    while(~scanf("%d",&D)) {
        if(D == -1) break;
        x[0] = D/sm;
        x[1] = D/mh;
        x[2] = D/sh;
        y[0] = (360.0-D)/sm;
        y[1] = (360.0-D)/mh;
        y[2] = (360.0-D)/sh;
        double st , ed;
        double ans = 0;
        for(m[0] = x[0] , n[0] = y[0] ; m[0]<=43200 ; m[0] += t_sm , n[0] += t_sm) { 
           for(m[1] = x[1] , n[1] = y[1] ; m[1] <= 43200 ; m[1] += t_mh , n[1] += t_mh) {
                if(m[0] > n[1]) continue;
                if(n[0] < m[1]) break;
                for(m[2] = x[2] , n[2] = y[2] ; m[2] <= 43200 ; m[2] += t_sh , n[2] += t_sh) {
                    if(n[2] < m[1] || n[2] < m[0]) continue;
                    if(m[2] > n[0] || m[2] > n[1]) break;
                    st = Max(m[0] , m[1] , m[2]);
                    ed = Min(n[0] , n[1] , n[2]);
                    if(ed > st) ans += ed - st;
                }
            }     
        }         /*取交集 记录区间的过程*/
        printf("%.3lf\n",ans/432.0);
    } 
}