hdoj 1006 Tick and Tick解题报告

ACM

发布日期: 2016-02-09

文章字数: 1k

阅读时长: 5 分

阅读次数:

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

**

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

一看，:-O哎呀好简单，一个公式解决：概率=[（360-3D）/360]*[（360-3D）/360],

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    float D,d;
    while(scanf("%f",&D)&&D!=-1)
    {
        d=360-3*D;
        printf("%.3f\n",d*d/1296);
    }
    return 0;
}

然而，，，还是图样图森破，在D=90时，得出答案为6.250，而标答是6.251，我还天真的以为在误差允许范围之类Orz，，，

做了好久无果，参考大神的代码，用角速度是没错的，发现了自己的计算方式一个致命的错误，我将三个指针当做完全不相干的进行计算，然而三个指针之间是有固定的位置关系的，所以不能单独计算一个小时的情况作为整个概率，参考大神的博客，采取暴力遍历720min的方式：

#include<iostream>
#include<stdio.h>
using namespace std;
float D;
struct sets      //存储区间上下界
{
    double low,up;
};
double max(double a,double b){
    if(a>b)return a;
    else return b;
}
double min(double a,double b){
    if(a<b)return a;
    else return b;
}
sets solve1(double a,double b);// 求 D<=|ax+b|<360-D 的解
sets solve2(double a,double b);// 求 D<=|ax+b|<360-D 的解
sets coti(sets a,sets b);   //取交集
int main()
{
    while(scanf("%f",&D)&&D!=-1)
    {
        double rel=0,a[3],b[3];  //这里一定要注意!!!
        a[0]=-11.0/120;       //不能写成a[0]=-11/120;
        a[1]=-6.0+1.0/120;    //不能写成a[1]=-6+1/120;
        a[2]=-5.9;            //精度问题一定要注意！！！
        sets ans[3][2];
        for (int h = 0; h <12; h += 1)
        {
            for (int m = 0; m < 60; m += 1)
            {
                b[0]=30*h-5.5*m;
                b[1]=30*h+0.5*m;
                b[2]=6*m;
/* 求3个绝对值不等式的解集 存到answer中answer[0][0] answer[0][1]要取并集剩下两个也是*/
                for (int i = 0; i < 3; i += 1)
                {
                    ans[i][0]=solve1(a[i],b[i]);
                    ans[i][1]=solve2(a[i],b[i]);
                }
                 /* 取过交集后，需要将3个式子的结果取并集 所以采用下面的方法 */
                for (int i = 0; i < 2; i += 1)
                {
                    for (int j = 0; j < 2; j += 1)
                    {
                        for (int k = 0; k < 2; k += 1)
                        {
                            sets ss=coti(coti(ans[0][i],ans[1][j]),ans[2][k]);
                            rel+=ss.up-ss.low;
                        }
                    }
                }
            }

        }
        printf("%.3f\n",rel/432);
    }
    return 0;
}
sets solve1(double a,double b)  //D<=|ax+b|<=360-D 分类解1
{
    sets ret;
    ret.up=min(-b/a,(D-b)/a);
    ret.low=(360.0-D-b)/a;
    if(ret.up>60)ret.up=60;
    if(ret.low<0)ret.low=0;
    if(ret.low>=ret.up)ret.low=ret.up=0;
    return ret;

}
sets solve2(double a,double b)  //D<=|ax+b|<=360-D 分类解2
{
    sets ret;
    ret.up=(360.0-D+b)/(-a);
    ret.low=max(-b/a,-(D+b)/a);
    if(ret.up>60)ret.up=60;
    if(ret.low<0)ret.low=0;
    if(ret.low>=ret.up)ret.low=ret.up=0;
    return ret;
}
sets coti(sets a,sets b)    //取交集
{
    sets p;
    p.low=a.low>b.low?a.low:b.low;
    p.up=a.up<b.up?a.up:b.up;
    if(p.low>p.up)p.low=p.up=0;
    return p;
}

这题其实并不是很难，但是对于题意的理解很重要，如果一开始就没有将他当成是离散的去做的话，估计很多人都能很快想到正确算法，可惜我虽然想到不用离散，却入了另外一个坑，对于题意的把握还是需要加强练习的。

crazyX

http://blog.jingwei.site/2016/02/09/hdoj1006/