ball_by_momodi.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/*
 * Author: [e-mail]
 * Created Time:  2/21/2009 3:19:07 PM
 * File Name: ball.cpp
 * Description: It's a very very long code that no one what to read it.
 Do not use 'sin' or 'cos' or 'acos' or 'asin'; that things will cause precision error.
 The test cases of this problem are hard to creat, so if you pass all the test cases, that doesn't mean your code are right.
 There may be some special cases we didn't find.
 If you know that cases, plz mail it to me. We'll appreciate it.
 
 There is another version of this problem which want to be known the shortest path with the radius we have already known.
 I think the algorithm of this two problem are the same.
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;
#define out(x) fprintf(stderr, "%s: %lld\n", #x, (long long)(x))
#define SZ(v) ((int)(v).size())
#define SQR(v) ((v) * (v))
const int maxint=-1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

const double eps = 1e-9;
int sgn(const double &a) {
    return (a > eps) - (a < -eps);
}

double sqr(const double &a) {
    return a * a;
}

struct P {
    double x, y;
    
    P(const double &_x, const double &_y)
        :x(_x), y(_y) {}
    
    P() {}
    
    bool operator < (const P &a) const {
        return sgn(x - a.x) < 0 or (sgn(x - a.x) == 0 and sgn(y - a.y) < 0);
    }
    
    bool operator == (const P &a) const {
        return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
    }
    
    bool operator != (const P &a) const {
        return sgn(x - a.x) != 0 || sgn(y - a.y) != 0;
    }
    
    P operator + (const P &a) const {
        return P(x + a.x, y + a.y);
    }
    
    P operator - (const P &a) const {
        return P(x - a.x, y - a.y);
    }
    
    P operator * (const double a) const {
        return P(x * a, y * a);
    }
    
    P operator / (const double &a) const {
        return P(x / a, y / a);
    }
    
    P turn_left() const {
        return P(-y, x);
    }
    
    P turn_right() const {
        return P(y, -x);
    }
    
    P trunc(double d) {
        d /= sqrt(x * x + y * y);
        return P(x * d, y * d);
    }
    
    void input() {
        scanf("%lf %lf", &x, &y);
    }
    
    void output() const {
        printf("P: %lf %lf\n", x, y);
    }
};

double cross(const P &a, const P &b, const P &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

double dmul(const P &a, const P &b, const P &c) {
    return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);
}

double dist(const P &a, const P &b) {
    return sqrt(SQR(a.x - b.x) + SQR(a.y - b.y));
}

double dist2(const P &a, const P &b) {
    return SQR(a.x - b.x) + SQR(a.y - b.y);
}
double point_line_dist(const P &a, const P &S, const P &T) {
    return abs(cross(a, S, T)) / dist(S, T);
}


P S, T;
int N, L, W, H;

struct Mtx {
    double minx, maxx, miny, maxy, h;
    
    Mtx(const double &_minx, const double &_maxx, const double &_miny, const double &_maxy, const double &_h)
        :minx(_minx), maxx(_maxx), miny(_miny), maxy(_maxy), h(_h) {
            gen();
        }
    
    Mtx(const double &_minx, const double &_maxx, const double &_miny, const double &_maxy)
        :minx(_minx), maxx(_maxx), miny(_miny), maxy(_maxy) {
            gen();
        }
    
    Mtx() {}
    
    P d[4];
    
    void gen() {
        d[0] = P(minx, miny);
        d[1] = P(minx, maxy);
        d[2] = P(maxx, maxy);
        d[3] = P(maxx, miny);
    }
    
    const P &operator [] (const int &index) const {
        if (index == 4) {
            return d[0];
        }
        return d[index];
    }
    
    P &operator [] (const int &index) {
        if (index == 4) {
            return d[0];
        }
        return d[index];
    }
    
    void output() const {
        printf("M: %.2lf %.2lf %.2lf %.2lf\n", minx, maxx, miny, maxy);
    }
};

bool in_range(const double &a, const double &s, const double &t) {
    return sgn(a - s) > 0 && sgn(a - t) < 0;
}

bool in_mtx(const P &a, const Mtx &m) {
    return in_range(a.x, m.minx, m.maxx) && in_range(a.y, m.miny, m.maxy);
}

struct C {
    P mid;
    double r;
    
    C(P _mid, double _r)
        :mid(_mid), r(_r) {}
    
    C() {}
    
    bool in(const C &a) const {
        return sgn(SQR(r - a.r) + dist2(mid, a.mid)) < 0;
    }
    
    bool operator == (const C &a) const {
        return mid == a.mid && sgn(r - a.r) == 0;
    }
    
    bool operator != (const C &a) const {
        return mid != a.mid || sgn(r - a.r) != 0;
    }
    
    void output() const {
        printf("C: %.2lf %.2lf %.2lf\n", mid.x, mid.y, r);
    }
};

vector<Mtx> mtx;
vector<Mtx> m;
vector<C> c;
vector<P> circle_point[200];
vector<int> f;
map<P, int> id;
int &find_id(const P &a) {
    if (id.count(a)) {
        return id[a];
    }
    f.push_back(f.size());
    return id[a] = SZ(id) - 1;
}

int find_father(int v) {
    if (v != f[v]) {
        return f[v] = find_father(f[v]);
    }
    return v;
}
bool uno(const P &a, const P &b) {
    int fa = find_father(find_id(a)), fb = find_father(find_id(b));
    f[fa] = fb;
    return find_father(0) == find_father(1);
}

bool on_circle(const P &a, const C &cir) {
    return sgn(dist2(a, cir.mid) - SQR(cir.r)) == 0;
}

bool in_circle(const P &a, const C &cir) {
    return sgn(dist2(a, cir.mid) - SQR(cir.r)) < 0;
}

bool in_segment(const P &a, const P &S, const P &T) {
    return sgn(dmul(a, S, T)) < 0;
}

bool line_circle_cross(const P &S, const P &T, const C &cir, P &a, P &b) {
    double dd = cross(S, T, cir.mid) / dist(S, T);
    if (sgn(abs(dd) - cir.r) >= 0) {
        return false;
    }
    double ll = sqrt(abs(sqr(cir.r) - sqr(dd)));
    P p = (T - S).turn_right().trunc(dd);
    a = cir.mid + p + (T - S).trunc(ll);
    b = cir.mid + p + (S - T).trunc(ll);
    return true;
}

bool segment_circle_cross(const P &S, const P &T, const C &cir) {
    P a, b;
    if (line_circle_cross(S, T, cir, a, b)) {
        if (in_segment(a, S, T) || in_segment(b, S, T) || in_segment((a + b) / 2, S, T)) {
            return true;
        }
    }
    return false;
}

bool segment_cross(const P &a, const P &b, const P &c, const P &d) {
    double s1 = cross(a, b, c);
    double s2 = cross(a, b, d);
    if (sgn(s2 - s1) == 0) {
        return false;
    }
    P ans = (c * s2 - d * s1) / (s2 - s1);
    return in_segment(ans, a, b) && in_segment(ans, c, d);
}

bool segment_mtx_cross(const P &S, const P &T, const Mtx &mm) {
    for (int i = 0; i < 4; ++i) {
        if (segment_cross(S, T, mm[i], mm[i + 1])) {
            return true;
        }
    }
    return false;
}