首页 > ACM题库 > HDU-杭电 > hdu 2468 Experiment on a … “Cable”-凸包问题-[解题报告]C++
2014
01-26

hdu 2468 Experiment on a … “Cable”-凸包问题-[解题报告]C++

Experiment on a … “Cable”

问题描述 :

The head technical person, Joey, at ACM (Association for Cyberspace Management)has just received a weird cable-like device � supposedly invented by programmers during a competition � for inspection.

The device may be viewed as a straight bi-directional cable, which can be used for transmitting arbitrary number of data packages simultaneously. The speed with which each package is sent will be pre-determined by the device and furthermore may vary within a certain range; however it will remain constant throughout each package’s entire transmission process. The time it takes for a single data package with speed V to arrive at the opposite end of the cable is thus L/V, where L is the length of the cable.

In addition, the user may sometimes send a fixed-speed “detector” package,
which is capable of reporting the number of data packages alongside itself at any time.

Finding this device highly amusing, Joey decides to perform an experiment on the odd “cable”. He has scheduled N packages to be sent from the left side and another M to be sent from the other side of the cable; also, he has calculated the possible speed range for each data package. With this information in hand, Joey wants to estimate the effectiveness of a detector he will send. For a detector that departs at a certain time, its effectiveness can be represented as a real number in the range [0..1], which is simply the ratio of the time during which the detector has a chance of reporting all N + M packages (explained below) to the total time.

If Joey sends the detector at an arbitrary time in [S, T] with speed V from the left side of the cable, what is the average effectiveness he can achieve?
Note: For a detector to have a chance of reporting all N + M packages at time T0, the device must be able to schedule all data packages with such speeds so that all can share the same position with the detector at time T0.

输入:

There are multiple test cases in the input file.
Each test case starts with one integer, L ( 1 ≤ L ≤ 106), the length of the cable.
The next line contains one integer, N, the number of packages Joey will send from the
left side, followed by N lines, the ith line with three real numbers, MinVi, MaxVi, and Leavei(1≤MinVi≤MaxVi), which are the minimum speed, maximum speed, and
departure time for package i , respectively. Another (M + 1) lines follow, describing the
packages departing from the right side. The last line of the input contains three real numbers, S, T and V (T – S ≥ 1), whose meanings are described above.
The total number of packages Joey sent will be in the interval [1,5000]. It is
guaranteed that the speed of any data packet, including that of the detector, will be no less than 0.01; also, all real numbers in the input will be given with at most two digits after the decimal point, and will belong to the interval: [0 , 106].
Two successive test cases are separated by a blank line. A case with L = 0
indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
Each test case starts with one integer, L ( 1 ≤ L ≤ 106), the length of the cable.
The next line contains one integer, N, the number of packages Joey will send from the
left side, followed by N lines, the ith line with three real numbers, MinVi, MaxVi, and Leavei(1≤MinVi≤MaxVi), which are the minimum speed, maximum speed, and
departure time for package i , respectively. Another (M + 1) lines follow, describing the
packages departing from the right side. The last line of the input contains three real numbers, S, T and V (T – S ≥ 1), whose meanings are described above.
The total number of packages Joey sent will be in the interval [1,5000]. It is
guaranteed that the speed of any data packet, including that of the detector, will be no less than 0.01; also, all real numbers in the input will be given with at most two digits after the decimal point, and will belong to the interval: [0 , 106].
Two successive test cases are separated by a blank line. A case with L = 0
indicates the end of the input file, and should not be processed by your program.

样例输入:

5
1
5.00 10.00 2.00
2
10.05 11.50 0.05
1.68 2.00 0.01
3.00 4.00 1000
5
1
1.25 2.50 1.0
0
1.00 5.00 2.50
0

样例输出:

Case #1: 0.00000
Case #2: 0.25000

如图,横坐标为时间轴,纵坐标为相对起点的位移,斜率为速度。

设C为起点发出的包,发出时间为1,速度为1~2。

设D为终点发出的包,发出时间为2,速度为1~2。

A、B为探测器发出时间范围2~5,速度为4。

由图可看出,发包的时间-位移相叠的范围为可能全部抓包的范围,称有效范围。

在探测器的时间-位移范围内的有效范围/探测器时间-位移范围即探测器全部抓包的平均工作效率。

对所有速度区间、探测器时间-位移区间、起点终点区间 做半平面交,得到凸包面积除以探测器时间-位移区间面积可得解。

精度要求挺高的,eps注意一下。

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 const int maxn = 5111;
 const double eps = 1e-12;
 const double pi = acos(-1.0);
 typedef struct{double x, y;}Point;
 int dcmp(double x) {return (x > eps) - (x < -eps);}
 inline double det(double x1, double y1, double x2, double y2)
 {return x1 * y2 - x2 * y1;}
 double cross(Point a, Point b, Point c)
 {return det(b.x -a.x, b.y - a.y, c.x - a.x, c.y - a.y);}
 bool EqualPoint(Point a, Point b)
 {return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;}
 typedef struct{Point s, e;double ang, d;}Line;
 Point MakePoint(double xx, double yy)
 {Point res;res.x = xx, res.y = yy;return res;}
 void SetLine(Point a, Point b, Line &l)
 {
     l.s = a;
     l.e = b;
     l.ang = atan2(b.y - a.y, b.x - a.x);
     if(dcmp(a.x - b.x)) l.d = (a.x * b.y - b.x * a.y) / fabs(a.x - b.x);
     else l.d = (a.x * b.y - b.x * a.y) / fabs(a.y - b.y);
 }
 bool Parallel(const Line &la, const Line &lb)
 {
     return !dcmp( (la.e.x - la.s.x) * (lb.e.y - lb.s.y) -
             (la.e.y - la.s.y) * (lb.e.x - lb.s.x) );
 }
 Point CrossPoint(const Line &la, const Line &lb)
 {
     Point res;
     double u = cross(la.s, la.e, lb.s), v = cross(la.e, la.s, lb.e);
     res.x = (lb.s.x * v + lb.e.x * u) / (u + v);
     res.y = (lb.s.y * v + lb.e.y * u) / (u + v);
     return res;
 }
 int CompL(const void *a, const void *b)
 {
     Line la = *(Line*)a, lb = *(Line*)b;
     if(dcmp(la.ang - lb.ang)) return la.ang > lb.ang ? 1 : -1;
     return la.d > lb.d ? 1 : -1;
 }
 
 Line deq[maxn];
 bool HalfPanelCross(Line l[], int n, Point cp[], int &m)
 {
     int i, tn;
     m = 0;
     qsort(l, n, sizeof(Line), CompL);
     for(i = tn = 1; i < n; ++ i)
         if(dcmp(l[i].ang - l[i - 1].ang))
             l[tn ++] = l[i];
     n = tn;
     int front = 0, rear = 1;
     deq[0] = l[0], deq[1] = l[1];
     for(i = 2; i < n; ++ i)
     {
         if(Parallel(deq[rear], deq[rear - 1]) ||
             Parallel(deq[front], deq[front + 1]))
             return false;
         while(front < rear && dcmp( cross(l[i].s, l[i].e,
             CrossPoint(deq[rear], deq[rear - 1])) ) < 0) -- rear;
         while(front < rear && dcmp( cross(l[i].s, l[i].e,
             CrossPoint(deq[front], deq[front + 1])) ) < 0) ++ front;
         deq[++ rear] = l[i];
     }
     while(front < rear && dcmp( cross(deq[front].s, deq[front].e,
         CrossPoint(deq[rear], deq[rear - 1])) ) < 0) -- rear;
     while(front < rear && dcmp( cross(deq[rear].s, deq[rear].e,
         CrossPoint(deq[front], deq[front + 1])) ) < 0) ++ front;
     if(rear <= front + 1) return false;
     for(i = front; i < rear; ++ i)
         cp[m ++] = CrossPoint(deq[i], deq[i + 1]);
     if(front < rear + 1)
         cp[m ++] = CrossPoint(deq[front], deq[rear]);
     m = unique(cp, cp + m, EqualPoint) - cp;
     for(i = 0; i < m; ++ i)
     {
         if(dcmp(cp[i].x) == 0) cp[i].x = 0;
         if(dcmp(cp[i].y) == 0) cp[i].y = 0;
     }
     return true;
 }
 double PolygonArea(Point p[], int n)
 {
     if(n < 3) return 0.0;
     double s = p[0].y * (p[n - 1].x - p[1].x);
     p[n] = p[0];
     for(int i = 1; i < n; ++ i)
         s += p[i].y * (p[i - 1].x - p[i + 1].x);
     return fabs(s * 0.5);
 }
 Line l[maxn << 2];
 Point p[maxn << 2];
 double len;
 int n, m, ltp;
 double maxv, minv, ti;
 double start, end, v;
 int main()
 {
     int ca = 0;
     while(scanf("%lf", &len), dcmp(len))
     {
         ltp = 0;
         scanf("%d", &n);
         while(n --)
         {
             scanf("%lf%lf%lf", &minv, &maxv, &ti);
             SetLine(MakePoint(ti, 0), MakePoint(ti + 1, minv), l[ltp ++]);
             SetLine(MakePoint(ti + 1, maxv), MakePoint(ti, 0), l[ltp ++]);
         }
         scanf("%d", &m);
         while(m --)
         {
             scanf("%lf%lf%lf", &minv, &maxv, &ti);
             SetLine(MakePoint(ti + 1, len - minv), MakePoint(ti, len), l[ltp ++]);
             SetLine(MakePoint(ti, len), MakePoint(ti + 1, len - maxv), l[ltp ++]);
         }
         scanf("%lf%lf%lf", &start, &end, &v);
         printf("Case #%d: ", ++ ca);
         SetLine(MakePoint(0, 0), MakePoint(1, 0), l[ltp ++]);
         SetLine(MakePoint(1, len), MakePoint(0, len), l[ltp ++]);
         SetLine(MakePoint(start + 1, v), MakePoint(start, 0), l[ltp ++]);
         SetLine(MakePoint(end, 0), MakePoint(end + 1, v), l[ltp ++]);
         if(!HalfPanelCross(l, ltp, p, n)){printf("0.00000\n"); continue;}
         printf("%.5f\n", PolygonArea(p, n) / (end - start) / len + eps);
     }
     return 0;
 }

解题转自:http://www.cnblogs.com/CSGrandeur/archive/2012/09/10/2679452.html


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。