acm时分秒针角度问题

原题来源：杭电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

0
120
90
-1

 

 

Sample Output

100.000
0.000
6.251

 

该题目要计算一天中时针、分针、秒针之间角度大于某一角度的概率。最朴素的算法是模拟每秒（每0.1秒或0.01秒）时计算三个针子之间角度，但计算量超大。以下java程序便是一例，由于计算量过大，会超时，但如减小计算量，精度又无法满足需求：

 

 import java.io.*;
import java.util.*;

public class P1006_2 {

    public static void main(String args[]) throws IOException{
        Scanner sin = new Scanner(System.in);
        int count ;
        double data[] = new double[3];
        float distance ;
        distance = sin.nextFloat();
       
        while((int)distance != -1){
            count = 0;
            if(distance >=120)
                System.out.println("0.000");
            else
            {

               //12小时分时秒针重合一次，每小时时分秒针分别走30，360，360*60度
                for(int i = 0;i<12;i++)                         
               //每小时均分30份，每份时时分秒针分别走1，12，720度   

                   for(int j=0;j<30;j++)
              // 每份再均分1000小份

                       for(int k=0;k<1000;k++){
                            data[0] = (i * 30 + j + 0.001 * k);
                            data[1] = (j * 12 + 0.012 * k);
                            data[2] = (k* 0.72)%360;
                            Arrays.sort(data);
                            if(data[1]-data[0]>=distance&data[2]-data[1]>=distance&360+data[0]-data[2]>=distance)
                                count ++;
                        }
                double percent = (double)count /360/10;
                System.out.printf("%f\n",percent);
            }
            distance = sin.nextFloat();
                      
        }
    }
}

不能AC，这是个大问题。后来从网上得到一个巧妙的算法，其原理是以空间换时间。其源程序（c++）如下：

 

#include <cstdio>
#include <iostream>
using namespace std;

inline double max(double a,double b,double c)
{
a= a > b ? a: b;
a= a > c ? a: c;
return a;
}
inline double min(double a,double b,double c)
{
a= a < b ? a: b;
a= a < c ? a: c;
return a;
}
int main()
{
double hdans;
double dsm[1444],dsh[1444],dmh[26];
//dsm存放秒针与分针之间的角度，dsh存放秒针与时针之间的角度
//dmh存放分针与时针之间的角度。
double s,m,h;

s=3600.0000/59;
m=43200.0000/719;
h=43200.0000/11;

while(cin >> hdans && hdans !=-1)
{
int i,j;
int sp[2],mp[2],hp[2];
double sum=0;
double x=0,y=0;
dsm[0] = (10*hdans)/59;
dsh[0] = (120*hdans)/719;
dmh[0] = (120*hdans)/11;

dsm[1] = s-dsm[0];
dsh[1] = m-dsh[0];
dmh[1] = h-dmh[0];

for(i=2,j=3; ;i+=2,j+=2)
{
dsm[i] = dsm[i-2]+s;
dsm[j] = dsm[j-2]+s;
if(dsm[i]>43200 && dsm[j]>43200)
break;
}
for(i=2,j=3;;i+=2,j+=2)
{
dsh[i] = dsh[i-2]+m;
dsh[j] = dsh[j-2]+m;
if(i==1436)
i=1436;
if(dsh[i]>43200 && dsh[j]>43200)
break;
}
for(i=2,j=3;;i+=2,j+=2)
{
dmh[i] = dmh[i-2]+h;
dmh[j] = dmh[j-2]+h;
if(dmh[i]>43200 && dmh[j]>43200)
break;
}
//以上代码用来根据hdans初始化dsm，dsh，dmh；
sp[0]=mp[0]=hp[0]=0;
sp[1]=mp[1]=hp[1]=1;
//sp,mp,hp分别为dsm，dsh，dmh的上下界指针。
while(y<=43200 && x<=43200)
{
x=max(dsm[sp[0]],dsh[mp[0]],dmh[hp[0]]);
y=min(dsm[sp[1]],dsh[mp[1]],dmh[hp[1]]);
if(x<y)
sum+=y-x;

if(y==dsm[sp[1]]) {sp[0]+=2;sp[1]+=2;}
if(y==dsh[mp[1]]) {mp[0]+=2;mp[1]+=2;}
if(y==dmh[hp[1]]) {hp[0]+=2;hp[1]+=2;}
}
printf("%.3f\n",sum/432);
}//while
return 0;
}

 

其中，s，m，h分别表示秒针与分针，秒针与时针，分针与时针重合一次所需要的时间。

dsm，dsh，dmh数组一分为二，偶下标元素表示秒针与分针，秒针与时针，分针与时针之间角度满足时所对应的开始时间，而奇下标元素则表示不满足时所对应的开始时间。

   很是巧妙！足见偶学习的空间还是很大的。o(∩_∩)o...哈哈 加油~