Rain on your Fat brother

Question

Problem Description
After retired form the ACM/ICPC competition, Fat brother starts his civil servant’s life with his pretty girl friend Maze. As far as we known for this holy job, we can imagine how a decadent life they are dealing with!

But one day, Fat brother and Maze have a big quarrel because of some petty things and Maze just run away straight from him. It’s raining cats and dogs outside, our hero Fat brother feel very worried about the little princess so he decide to chase her. As Maze is a tsundere girl, she would feel angry when she touches the rain until she meets the Fat brother.

To simplify this problem, we can just consider each person as a point running along the X coordinate from right to left and the rain as a combination of an isosceles triangle and a half round. The speed of Maze is v1 unit per second and the speed of Fat brother is v2 unit per second (v1 < v2). The place where they have a quarrel is (x, 0) and Fat brother start to chase Maze after T second. You can assume that the rain is doing the uniform linear motion (drop with the same speed forever). Your task is calculating how long (time) the Maze is in the rain. The Maze is considered in the rain even if the point representing her is just touch the border. See the picture for more detail.

Input
The first line contains only one integer T (T<=200), which is the number of test cases. For each test case, first line comes five positive integer v1, v2, v, t, x (v1<v2). v1 is the speed of Maze, v2 is the speed of Fat brother, v is the speed of the rain, you can assume that all rain is in a same speed, t means Fat brother starts to chase Maze after t second, x means they have a quarrel in (x, 0). Then a line with an integer n means that there is n rain begin to drop when Maze start running, 1<=n<=1000. Then n lines describe the rain. Each line contains four integers x0, y0, r, h. (x0, y0) is the center of the circle, r is the radius of the circle, h is the height of the triangle. All the number mentioned before except x0 are positive and no large than 1000. x0 is no large than 1000 and no less than -1000. Note that the point (x, 0) may in the rain in the beginning. Two rains may intersect with each other. See the picture for more detail.

Output
For each test case, output the case number first, then output how long (time) Maze is in the rain, round to 4 digits after decimal point.

Sample Input
4
1 2 1 100 1
1
1 1 1 1
1 2 1 100 1
1
2 1 1 1
1 2 1 100 1
1
-9 9 10 10
2 3 1 100 1
1
-9 9 10 10

Sample Output
Case 1: 1.0000
Case 2: 0.0000
Case 3: 12.0534
Case 4: 8.0428

Answer 1

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>

#define FOR(i, n) for(int i = 0; i < n; i++)
#define MEM(array) memset(array, 0, sizeof(array))
#define eps 1e-7
#define INF 1e10
#define PI acos(-1.0)
using namespace std;
inline int sgn(const double &x){return x > eps ? 1 : (x < -eps ? -1 : 0);}
inline double sqr(const double &x){return x * x;}
struct Point{
        double x, y;
        Point(){}
        Point(const double &xx, const double &yy):x(xx), y(yy){}
        Point operator + (const Point &a)const {
            return Point(x + a.x, y + a.y);
        }
        Point operator - (const Point &a)const {
            return Point(x - a.x, y - a.y);
        }
        Point operator * (const double &w)const{
            return Point(x * w, y * w);
        }
        Point operator / (const double &w)const{
            return Point(x / w, y / w);
        }
        friend Point operator * (const double &w, const Point &a){
            return Point(a.x * w, a.y * w);
        }
        friend double det(const Point &a, const Point &b){
            return a.x * b.y - a.y * b.x;
        }
        friend double dot(const Point &a, const Point &b){
            return a.x * b.x + a.y * b.y;
        }
        friend double dist(const Point &a, const Point &b){
            return (b - a).len();
        }
        double len()const{
            return sqrt( dot(*this, *this));
        }
        Point norm()const{
            double vLen = len();
            return Point(x / vLen , y / vLen);
        }
        Point rotate(double angle){
            double x1  = x * cos(angle) - y * sin(angle);
            double y1  = x * sin(angle) + y * cos(angle);
            return Point(x1, y1);
        }
        bool operator < (const Point &a)const {
            return sgn(x - a.x) < 0 || (sgn(x  - a.x) == 0 && sgn(y - a.y) > 0);
        }
        bool operator > (const Point &a)const {
            return sgn(x - a.x) > 0 || (sgn(x  - a.x) == 0 && sgn(y - a.y) < 0);
        }
        bool operator == (const Point &a)const {
            return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
        }
        void in(){
            scanf("%lf %lf", &x, &y);
        }
        void out()const{
            printf("%.4f   %.4f\n", x, y);
        }
};
struct Line{
    Point s, t;
    Line(){}
    Line(const Point &ss, const Point &tt):s(ss), t(tt){}
    friend bool lineParallelLine(const Line &l1, const Line &l2){
        return sgn(det(l1.t - l1.s, l2.t - l2.s)) == 0;
    }
    friend bool isPointOnLine(const Point &a, const Line &line){
        Point va = line.s - a, vb = line.t - a;
        int res1 = sgn(det(va, vb));
        if(res1 != 0)return false;
        return sgn( dot(va, vb) ) <= 0;
    }
    friend double pointDistLine(const Point &p, const Line &line){
        return fabs(det(p - line.s, line.t - line.s)/ (line.t- line.s).len());
    }
    friend Point pointProjLine(const Point &p, const Line &line){
        return line.s + ( line.norm() * dot(p - line.s, line.t - line.s)/ (line.t - line.s).len() );
    }
    friend bool sameSide(const Line &line, const Point &a, const Point &b){
        int res1 = sgn(det( a - line.s, line.t - line.s));
        int res2 = sgn(det( b - line.s, line.t - line.s));
        return res1 * res2 > 0;
    }
    friend vector<Point> lineInsectLine(const Line &l1, const Line &l2){
        vector<Point>res;
        if(lineParallelLine(l1, l2)){
                if( sgn(pointDistLine(l1.s, l2))==0 )res.push_back(l1.s);
                if( sgn(pointDistLine(l1.t, l2))==0 )res.push_back(l1.t);
        }else {
                Point vs = l1.s - l2.s, vl = l2.t - l2.s, vt = l1.t - l2.s;
                double s1 = det(vs, vl), s2 = det(vt, vl);
                res.push_back( (s1 * l1.t - s2 * l1.s)/(s1- s2));
        }
        return res;
    }
    Point norm()const{
        return (t - s).norm();
    }
     Point vec()const{
        return t - s;
    }
    void out()const{
        s.out();
        t.out();
    }
};
int numl;
struct Tri{
    Point a[3];
    Tri(){}
    Tri(const Point &aa, const Point &bb, const Point &cc){
        a[0] = aa; a[1] = bb; a[2] = cc;
    }

    friend vector<Point> triInsectLine(const Tri &tri, const Line &line){
        vector<Point>res, tt;
        for(int i = 0; i < 3; i++){
            Line linet(tri.a[i], tri.a[(i + 1)%3]);
            tt = lineInsectLine(line, linet);
            FOR(j, tt.size()){
                if(isPointOnLine(tt[j], linet))res.push_back(tt[j]);
            }
        }
        sort(res.begin(), res.end());
        int tn = unique(res.begin(), res.end()) - res.begin();
        res.resize(tn);
        return res;
    }
};
struct Cir{
    Point o;
    double r;
    Cir(){}
    Cir(const Point &p, const double &rr):o(p), r(rr){}
    friend vector<Point>  cirInsectLine(const Cir &cir, const Line &line){
        vector<Point>res;
        double dist = pointDistLine(cir.o, line);
        if(dist < cir.r){
            double len = sqrt(sqr(cir.r) - sqr(dist));
            Point re = pointProjLine(cir.o, line);
            Point tt1 = re - (line.norm() * len), tt2 = re + (line.norm() * len);
            if( sgn(tt1.y - cir.o.y) < 0) res.push_back(tt1);
            if( sgn(tt2.y - cir.o.y) < 0) res.push_back(tt2);
        }
        return res;
    }
    void in(){
        o.in();
        scanf("%lf",&r);
    }
};
Point endPoint, srcPoint;
Line mainLine, endLine;
struct Rain{
    Tri tri;
    Cir cir;
    Rain(){}
    friend Line rainInsectLine(const Rain &rain, const Line &line){
        vector <Point>res;
        vector<Point>res1 = triInsectLine(rain.tri, line);
        vector<Point>res2 = cirInsectLine(rain.cir, line);
        Point leftPoint = line.t, rightPoint = line.s;
        FOR(i, res1.size()){
            res.push_back(res1[i]);
        }
        FOR(i, res2.size()){
           res.push_back(res2[i]);
        }
        int len = res.size();
        if(len > 1){
            FOR(i, len){
                if(leftPoint > res[i])leftPoint = res[i];
                if(rightPoint < res[i])rightPoint = res[i];
            }
            if(leftPoint < line.s)leftPoint = line.s;
            if(rightPoint > line.t)rightPoint = line.t;
        }else {
            leftPoint = rightPoint;
        }
        return Line(leftPoint, rightPoint);
    }
    void in(){
        cir.in();
        double h;
        scanf("%lf", &h);
        Point a(cir.o.x - cir.r, cir.o.y), b(cir.o.x + cir.r, cir.o.y), c(cir.o.x, cir.o.y + h);
        tri = Tri(a, b, c);
    }
}rain[11111];
double va, vb, vr,  t, x;
int n;
Point vMain;
void init(){
    srcPoint = Point(x, 0);
    t += t *va/ (vb - va);
    vMain = Point(-va, vr);
    endPoint = srcPoint + vMain * t;
    mainLine = Line(endPoint, srcPoint);
}
struct pointR{
    Point p;
    int type;
    bool operator < (const pointR &a)const {
        return p < a.p;
    }
}pr[11111];
int ca = 0;
double ans = 0;
void solve(){
    ans = 0;
    FOR(i, n){
        Line line = rainInsectLine(rain[i], mainLine);
        pr[i * 2].p = line.s; pr[i * 2].type = 1;
        pr[i * 2 + 1].p = line.t; pr[i * 2 + 1].type = -1;
    }
    int cnt = 0;
    sort(pr, pr + 2 * n);
    FOR(i, 2 * n){
        if(cnt){
            ans += fabs( Line(pr[i -1].p, pr[i].p).vec().len());
        }
        cnt += pr[i].type;
    }
    printf("Case %d: %.4f\n", ++ca, ans / vMain.len());
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%lf %lf %lf %lf %lf", &va, &vb, &vr, &t, &x);
        scanf("%d", &n);
        FOR(i, n){
            rain[i].in();
        }
        init();
        solve();
    }
    return 0;
}
/*
2
1
1 2 1 5 0
1
-4 5 2 2
*/