hdu1006--Tick and Tick--时钟角度问题+区间求并求交

Tick and Tick

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 7811    Accepted Submission(s): 2154

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
        

Author PAN, Minghao  

Source ZJCPC2004  

Recommend JGShining  

题意很容易理解，

解法的话，

首先要知道时针转过的角度，分针转过的角度，秒针转过的角度和几点几分几秒的关系。

关系为：

hh=30*（h+ m/60 + s/3600）;

mm=6*( m+s/60 );

ss=6*s;

即求D<=|hh-mm|<=360-D

        D<=|hh-ss|<=360-D

        D<=|mm-ss|<=360-D

这样三个不等式的区间之交。

学到几点：

1.怎样求解不等式！以及不等式与系数正负的关系

2.怎样解决两个甚至多个区间的区间并的问题，即通过枚举区间达到求解的目的

3.怎样求解区间交。

4.时钟的指针角度问题

5.两个double型的数的比较方法，

6.结构体是可以直接通过等于号完成默认构造函数的。

代码思路很清晰，注释里说的很清楚了。

再看不懂的话，可以看kuangbin大神写的～～ http://www.cnblogs.com/kuangbin/archive/2011/12/04/2275470.html

//hdu 1006
//自己写的有关区间的第一道题
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1e-8;

double D;

//主要用来判断double a与double b是否相等
int dcmp(double a,double b)
{
    if(fabs(a-b)<eps)
        return 0;
    else
        return a-b>0?1:-1;
}

//区间结构体
struct interval
{
    double l;
    double r;
    /*
    这样重载加号（作为并集）是有问题的！！！！因为有可能两个区间没有连续的公共部分。
    interval operator +(const interval&temp) const
    {
        interval res;
        res.l=min(l,temp.l);
        res.r=max(r,temp.r);
        if(res.l>res.r) res.l=res.r=0; //判断是否为空集，由于该题只要求区间长度，所以全部赋值为0即可
        return res;
    }
    */
    //重载交集，这样写是对的
    interval operator *(const interval&temp) const
    {
        interval res;
        res.l=max(l,temp.l);
        res.r=min(r,temp.r);
        if(res.l>res.r) res.l=res.r=0; //判断是否为空集，由于该题只要求区间长度，所以全部赋值为0即可
        return res;
    }
};

//解决形如D<=a*x+b<=360-D的不等式,并和【0,60】取交集
interval solve(double a,double b)
{
    interval res;
    if(a>0)
    {
        res.l=(D-b)/a;
        res.r=(360-D-b)/a;
        if(res.l<0) res.l=0;
        if(res.r>60) res.r=60;
        if(res.l>res.r) res.l=res.r=0;
    }
    else
    {
        res.r=(D-b)/a;
        res.l=(360-D-b)/a;
        if(res.l<0) res.l=0;
        if(res.r>60) res.r=60;
        if(res.l>res.r) res.l=res.r=0;
    }
    return res;
}

//求解3个形如D<=|ax+b|<=360-D的不等式
double cal(int h,int m)
{
    double a,b;
    interval ans[3][2];

    //求D<=|hh-mm|<=360-D
    a=1.0/120-1.0/10; //1.0 is so important
    b=30*h+(1.0/2-6)*m;
    ans[0][0]=solve(a,b);    //不需要重载“=”运算符，因为有一个默认拷贝构造函数！
    ans[0][1]=solve(-a,-b);

    //求D<=|hh-ss|<=360-D
    a=1.0/120-6;
    b=30*h+0.5*m;
    ans[1][0]=solve(a,b);
    ans[1][1]=solve(-a,-b);

    //求D<=|mm-ss|<=360-D
    a=1.0/10-6;
    b=6*m;
    ans[2][0]=solve(a,b);
    ans[2][1]=solve(-a,-b);
    interval temp;
    double res=0;
    for(int i=0;i<2;++i)
    {
        for(int j=0;j<2;++j)
        {
            for(int k=0;k<2;++k)
            {
                temp=ans[0][i]*ans[1][j]*ans[2][k];
                res+=temp.r-temp.l;
            }
        }
    }
    return res;
}
int main()
{
    //freopen("input.txt","r",stdin);
    while(~scanf("%lf",&D))
    {
        double ans=0;
        if(dcmp(D,-1)==0)break;
        for(int h=0;h<6;++h) //已经是我能想到的最大的优化了，真心不知道那些0ms是怎么跑出来的
        {
            for(int m=0;m<60;++m)
            {
                ans+=cal(h,m);
            }
        }
        printf("%.3lf\n",2*ans*100.0/(60*60*12));
    }
    return 0;
}