杭电ACM1006

本题的核心是追击问题.时间是连续的,另外要注意区间的交运算.
程序的算法是:
已知秒针,分针,时针的速度分别为:
Vs=6度/s;Vm=1/10度/s;Vs=1/120度/s;
首先根据给出的角度生成三个指针夹角大于该角度的所有区间,然后求区间的交,并进行统计.

首先是三个针角度的函数：
秒针：6t
分针：(t%60)/10
时针：(t%3600)/120

a是题目给你的限制时间
a <= | 6*t-(t%60)/10| <= 360-a
a <= | 6*t-(t%3600)/120 | <= 360-a
a <= | (t%60)/10-(t%3600)/120 | <= 360-a
时间只要满足上市就是happytime

由于double类型不好取mod
我就把时间分割成一分钟一分钟
循环个720次。。。。所以说这样的方法比较暴力
不过据说有循环，不过我想不出来。。。

然后就只计算上边三个式子的交集。。。
浮点型的交集好烦。。
code:
#include
#include
#include
double num[14];
int hash[13];
int cmp(const void *a,const void *b)
{
return *(double *)a > *(double *)b ? 1 : -1;
}
void hh(double a ,double b)
{
int i;
double start,end;
start = 0;
end = a;
for(i=0;i<13;i++)
if(start <= num[i] && num[i+1] <= end)
hash[i] ++;
start = b;
end = 60;
for(i=0;i<13;i++)
if(start <= num[i] && num[i+1] <= end)
hash[i] ++;
}
void hhh(double a,double b)
{
int i;
if(b<0 || a>60)
return ;
for(i=0;i<13;i++)
if(a <= num[i] && num[i+1] <= b)
hash[i] ++;
}
double happytime(double ms,double hs,double a)
{
//a <= | 6*t-(t+ms)/10 | <= 360-a

//a <= | 6*t-(t+hs)/120 | <= 360-a

//a <= | (t+ms)/10-(t+hs)/120 | <= 360-a

//计算同时满足上边三个条件的t
double aa,ab,ac,ad,ba,bb,bc,bd,ca,cb,cc,cd,sum;

aa = (ms-a*10)/59;
ab = (ms+a*10)/59;
ac = (ms+10*a-3600)/59;
ad = (ms+3600-10*a)/59;

ba = (hs-12*ms-a*120)/11;
bb = (hs-12*ms+a*120)/11;
bc = (hs-12*ms+120*a-43200)/11;
bd = (hs-12*ms+43200-120*a)/11;

ca = (hs-a*120)/719;
cb = (hs+a*120)/719;
cc = (hs+120*a-43200)/719;
cd = (hs+43200-120*a)/719;

num[0] = 0;
num[1] = 60;
num[2] = aa;
num[3] = ab;
num[4] = ac;
num[5] = ad;
num[6] = ba;
num[7] = bb;
num[8] = bc;
num[9] = bd;
num[10] = ca;
num[11] = cb;
num[12] = cc;
num[13] = cd;

qsort(num,14,sizeof(num[0]),cmp);
memset(hash,0,sizeof(hash));
sum = 0;
hh(aa,ab);
hh(ba,bb);
hh(ca,cb);
hhh(ac,ad);
hhh(bc,bd);
hhh(cc,cd);
for(int i=0;i<13;i++)
if(hash[i]>=6)
sum += num[i+1] - num[i];
return sum;
}
int main()
{
int i,start;
double ans,a;
while(scanf("%lf",&a),a!=-1)
{
ans = 0;
start = 0;
for(i=0;i<720;i++)
{
if(i==109)
i = i;
ans += happytime(start%3600,start,a);
start += 60;
}
printf("%.3lf\n",ans*100/43200);
}
return 0;
}