如图，横坐标为时间轴，纵坐标为相对起点的位移，斜率为速度。
设C为起点发出的包，发出时间为1，速度为1~2。
设D为终点发出的包，发出时间为2，速度为1~2。
A、B为探测器发出时间范围2~5，速度为4。
由图可看出，发包的时间-位移相叠的范围为可能全部抓包的范围，称有效范围。
在探测器的时间-位移范围内的有效范围/探测器时间-位移范围即探测器全部抓包的平均工作效率。
对所有速度区间、探测器时间-位移区间、起点终点区间 做半平面交，得到凸包面积除以探测器时间-位移区间面积可得解。
精度要求挺高的，eps注意一下。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn = 5111; 8 const double eps = 1e-12; 9 const double pi = acos(-1.0); 10 typedef struct{ double x, y;}Point; 11 int dcmp(double x) { return (x > eps) - (x < -eps);} 12 inline double det(double x1, double y1, double x2, double y2) 13 { return x1 * y2 - x2 * y1;} 14 double cross(Point a, Point b, Point c) 15 { return det(b.x -a.x, b.y - a.y, c.x - a.x, c.y - a.y);} 16 bool EqualPoint(Point a, Point b) 17 { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;} 18 typedef struct{Point s, e;double ang, d;}Line; 19 Point MakePoint(double xx, double yy) 20 {Point res;res.x = xx, res.y = yy;return res;} 21 void SetLine(Point a, Point b, Line &l) 22 { 23 l.s = a; 24 l.e = b; 25 l.ang = atan2(b.y - a.y, b.x - a.x); 26 if(dcmp(a.x - b.x)) l.d = (a.x * b.y - b.x * a.y) / fabs(a.x - b.x); 27 else l.d = (a.x * b.y - b.x * a.y) / fabs(a.y - b.y); 28 } 29 bool Parallel(const Line &la, const Line &lb) 30 { 31 return !dcmp( (la.e.x - la.s.x) * (lb.e.y - lb.s.y) - 32 (la.e.y - la.s.y) * (lb.e.x - lb.s.x) ); 33 } 34 Point CrossPoint(const Line &la, const Line &lb) 35 { 36 Point res; 37 double u = cross(la.s, la.e, lb.s), v = cross(la.e, la.s, lb.e); 38 res.x = (lb.s.x * v + lb.e.x * u) / (u + v); 39 res.y = (lb.s.y * v + lb.e.y * u) / (u + v); 40 return res; 41 } 42 int CompL(const void *a, const void *b) 43 { 44 Line la = *(Line*)a, lb = *(Line*)b; 45 if(dcmp(la.ang - lb.ang)) return la.ang > lb.ang ? 1 : -1; 46 return la.d > lb.d ? 1 : -1; 47 } 48 49 Line deq[maxn]; 50 bool HalfPanelCross(Line l[], int n, Point cp[], int &m) 51 { 52 int i, tn; 53 m = 0; 54 qsort(l, n, sizeof(Line), CompL); 55 for(i = tn = 1; i < n; ++ i) 56 if(dcmp(l[i].ang - l[i - 1].ang)) 57 l[tn ++] = l[i]; 58 n = tn; 59 int front = 0, rear = 1; 60 deq[0] = l[0], deq[1] = l[1]; 61 for(i = 2; i < n; ++ i) 62 { 63 if(Parallel(deq[rear], deq[rear - 1]) || 64 Parallel(deq[front], deq[front + 1])) 65 return false; 66 while(front < rear && dcmp( cross(l[i].s, l[i].e, 67 CrossPoint(deq[rear], deq[rear - 1])) ) < 0) -- rear; 68 while(front < rear && dcmp( cross(l[i].s, l[i].e, 69 CrossPoint(deq[front], deq[front + 1])) ) < 0) ++ front; 70 deq[++ rear] = l[i]; 71 } 72 while(front < rear && dcmp( cross(deq[front].s, deq[front].e, 73 CrossPoint(deq[rear], deq[rear - 1])) ) < 0) -- rear; 74 while(front < rear && dcmp( cross(deq[rear].s, deq[rear].e, 75 CrossPoint(deq[front], deq[front + 1])) ) < 0) ++ front; 76 if(rear <= front + 1) return false; 77 for(i = front; i < rear; ++ i) 78 cp[m ++] = CrossPoint(deq[i], deq[i + 1]); 79 if(front < rear + 1) 80 cp[m ++] = CrossPoint(deq[front], deq[rear]); 81 m = unique(cp, cp + m, EqualPoint) - cp; 82 for(i = 0; i < m; ++ i) 83 { 84 if(dcmp(cp[i].x) == 0) cp[i].x = 0; 85 if(dcmp(cp[i].y) == 0) cp[i].y = 0; 86 } 87 return true; 88 } 89 double PolygonArea(Point p[], int n) 90 { 91 if(n < 3) return 0.0; 92 double s = p[0].y * (p[n - 1].x - p[1].x); 93 p[n] = p[0]; 94 for(int i = 1; i < n; ++ i) 95 s += p[i].y * (p[i - 1].x - p[i + 1].x); 96 return fabs(s * 0.5); 97 } 98 Line l[maxn << 2]; 99 Point p[maxn << 2];100 double len;101 int n, m, ltp;102 double maxv, minv, ti;103 double start, end, v;104 int main()105 {106 int ca = 0;107 while(scanf("%lf", &len), dcmp(len))108 {109 ltp = 0;110 scanf("%d", &n);111 while(n --)112 {113 scanf("%lf%lf%lf", &minv, &maxv, &ti);114 SetLine(MakePoint(ti, 0), MakePoint(ti + 1, minv), l[ltp ++]);115 SetLine(MakePoint(ti + 1, maxv), MakePoint(ti, 0), l[ltp ++]);116 }117 scanf("%d", &m);118 while(m --)119 {120 scanf("%lf%lf%lf", &minv, &maxv, &ti);121 SetLine(MakePoint(ti + 1, len - minv), MakePoint(ti, len), l[ltp ++]);122 SetLine(MakePoint(ti, len), MakePoint(ti + 1, len - maxv), l[ltp ++]);123 }124 scanf("%lf%lf%lf", &start, &end, &v);125 printf("Case #%d: ", ++ ca);126 SetLine(MakePoint(0, 0), MakePoint(1, 0), l[ltp ++]);127 SetLine(MakePoint(1, len), MakePoint(0, len), l[ltp ++]);128 SetLine(MakePoint(start + 1, v), MakePoint(start, 0), l[ltp ++]);129 SetLine(MakePoint(end, 0), MakePoint(end + 1, v), l[ltp ++]);130 if(!HalfPanelCross(l, ltp, p, n)){printf("0.00000\n"); continue;}131 printf("%.5f\n", PolygonArea(p, n) / (end - start) / len + eps);132 }133 return 0;134 }