2014
01-26

# 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

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

#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;
}

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