hdu 1006 Tick and Tick

http://acm.hdu.edu.cn/showproblem.php?pid=1006

　　题意不多说，这题是求一个概率。刚开始的时候我并没有思路，想了颇久，最后还是打算看看题解。网上的题解不好理解，但是当我看到一个找三种针之间速度的差距就可以计算出来，我就突然灵机一动，想到了先计算出两种针间每秒的变化速度，然后就像小学的追逐问题一样，计算出时间。一天是24小时，但是我们只需要计算前12个小时就可以了。

　　然后，将计算出的时间储存起来，变成区间，最后就把问题转变为区间取交的问题了！

　　运行的时间不会太长，15ms，跟网上某些说跟精度有关的算法不一样，我的是直接计算，所以精度不会影响结果！

代码如下（1y）：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 
  6 // degrees per second
  7 const double h_m = (360.0 - 30.0) / 3600;
  8 const double h_s = (360.0 * 60 - 30.0) / 3600;
  9 const double m_s = (360.0 * 60 - 360.0) / 3600;
 10 const double maxt = 43200;
 11 const double eps = 1e-6;
 12 const int maxn = 800;
 13 
 14 double max2(double a, double b){return a > b ? a : b;}
 15 double min2(double a, double b){return a < b ? a : b;}
 16 
 17 struct line{
 18     double s, t;
 19 }l1[maxn], l2[maxn], l3[maxn], ll[maxn << 2];
 20 
 21 bool in[maxn];
 22 
 23 bool cmp(line a, line b){
 24     if (fabs(a.s - b.s) > eps) return a.s < b.s;
 25     return a.t < b.t;
 26 }
 27 
 28 bool nocross(line a, line b){
 29     return a.s > b.t || b.s > a.t;
 30 }
 31 // 区间取交 sections intersection
 32 void calm(line a[], int n, line b[], int m, line c[], int &k){
 33     k = 0;
 34     if (!n || !m) return;
 35     int i = 0, j = 0, w;
 36     while (i < n && j < m){
 37         if (a[i].s < b[j].s){
 38             for (w = j; b[w].s < a[i].t && w < m; w++){
 39                 c[k].s = b[w].s;
 40                 c[k].t = min2(a[i].t, b[w].t);
 41                 k++;
 42             }
 43             j = w;
 44             i++;
 45             if (j && (!nocross(a[i], b[j - 1]))) j--;
 46         }
 47         else {
 48             for (w = i; a[w].s < b[j].t && w < n; w++){
 49                 c[k].s = a[w].s;
 50                 c[k].t = min2(a[w].t, b[j].t);
 51                 k++;
 52             }
 53             i = w;
 54             j++;
 55             if (i && (!nocross(a[i - 1], b[j]))) i--;
 56         }
 57     }
 58 }
 59 
 60 // deal with the problem
 61 double cal(double k){
 62     int T = 0;
 63     bool ref = true;
 64     double s, t;
 65     int n1, n2, n3, n;
 66 
 67     n1 = n2 = n3 = 0;
 68     while (ref){
 69          ref = false;
 70         s = 360.0 * T + k;
 71         t = 360.0 * (T + 1) - k;
 72 
 73         if (s / h_m < maxt){
 74             l1[n1].s = s / h_m;
 75             l1[n1].t = t / h_m;
 76             if (t / h_m > maxt) l1[n1].t = maxt;
 77             n1++;
 78             ref = true;
 79         }
 80         if (s / h_s < maxt){
 81             l2[n2].s = s / h_s;
 82             l2[n2].t = t / h_s;
 83             if (t / h_s > maxt) l2[n2].t = maxt;
 84             n2++;
 85             ref = true;
 86         }
 87         if (s / m_s < maxt){
 88             l3[n3].s = s / m_s;
 89             l3[n3].t = t / m_s;
 90             if (t / m_s > maxt) l3[n3].t = maxt;
 91             n3++;
 92             ref = true;
 93         }
 94         T++;
 95     }
 96     calm(l1, n1, l2, n2, ll, n);
 97     calm(l3, n3, ll, n, l1, n1); // calculate the intersection of three sections
 98 
 99     double sum = 0;
100     for (int i = 0; i < n1; i++){
101         sum += l1[i].t - l1[i].s;
102     }
103 // sum up the sections
104 
105     return sum * 100 / maxt;
106 }
107 
108 
109 bool deal(){
110     double D;
111 
112     scanf("%lf", &D);
113     if (D < -0.5) return false;
114     printf("%.3f\n", cal(D));
115 
116     return true;
117 }
118 
119 int main(){
120 #ifndef ONLINE_JUDGE
121     freopen("in", "r", stdin);
122     printf("h_m %f\nh_s %f\nm_s %f\n\n", h_m, h_s, m_s);
123 #endif
124     while (deal());
125 
126     return 0;
127 }

——written by Lyon