ball_felicia.cpp

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

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <list>
#include <map>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
template <class T> void get_max(T &a, const T &b) {b > a ? a = b : 1;}
template <class T> void get_min(T &a, const T &b) {b < a ? a = b : 1;}

#define SZ(x) (int((x).size()))
#define NEXT(x, n) ((x) == ((n) - 1) ? (0) : ((x) + 1))
#define sqr(x) ((x) * (x))

const double eps = 1e-6;
const double pi = acos(-1.0);

bool debug;

inline int sgn(const double &d) {
    return (d > eps) - (d < -eps);
}

struct point {
    double x, y;
    int id;
    point() {id = -1;}
    point(const double &_x, const double &_y) : x(_x), y(_y) {id = -1;}
    point(const point &s, const point &e) : x(e.x - s.x), y(e.y - s.y) {id = -1;}
    bool operator < (const point &b) const {
        return sgn(y - b.y) < 0 || (sgn(y - b.y) == 0 && sgn(x - b.x) < 0);
    }
    bool operator == (const point &b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    point operator + (const point &b) const {
        return point(x + b.x, y + b.y);
    }
    point operator - (const point &b) const {
        return point(x - b.x, y - b.y);        
    }
    point operator * (const double &s) const {
        return point(x * s, y * s);
    }
    point operator / (const double &s) const {
        return point(x / s, y / s);
    }
    double len2() const {
        return x * x + y * y;
    }
    double len() const {
        return sqrt(x * x + y * y);
    }
    point norm() const {
        double l = len();
        return point(x / l, y / l);
    }
    point tolen(const double &ll) const {
        double l = ll / len();
        return point(x * l, y * l);        
    }
    point turn_left() const {
        return point(-y, x);
    }
    point turn_left(const double &cos_t) const {
        double sin_t = sqrt(1 - sqr(cos_t));
        return point(cos_t * x - sin_t * y, sin_t * x + cos_t * y);
    }
    point turn_right() const {
        return point(y, -x);
    }
    point turn_right(const double &cos_t) const {
        double sin_t = sqrt(1 - sqr(cos_t));
        return point(cos_t * x + sin_t * y, -sin_t * x + cos_t * y);
    }
    void print() {
        printf("(%.2lf %.2lf) ", x, y);
    }
};
typedef point vec;

double dot(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}

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

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

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

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

double dist2(const point &a, const point &b) {
    return sqr(a.x - b.x) + sqr(a.y - b.y);
}

struct rt {
    double xmin, xmax, ymin, ymax;
    point p[4];
    rt() {}
    rt(const double &_xmin, const double &_ymin, const double &_xmax, const double &_ymax) : xmin(_xmin), xmax(_xmax), ymin(_ymin), ymax(_ymax) {
        p[0] = point(xmin, ymin);
        p[1] = point(xmax, ymin);
        p[2] = point(xmax, ymax);
        p[3] = point(xmin, ymax);
    }
};

struct circle {
    point o;
    double r;
    circle() {}
    circle(const point &_o, const double &_r) : o(_o), r(_r) {}
};

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

struct arc {
    point o, a, b;
    double r;
    arc() {}
    arc(const point &_o, const point &_a, const point &_b) : o(_o), a(_a), b(_b) {
        r = dist(o, a);
    }
    arc(const point &_o, const double &_r, const int &type) : o(_o), r(_r) {
        int type1 = (type + 1) % 4;
        a = point(o.x + r * dx[type], o.y + r * dy[type]);
        b = point(o.x + r * dx[type1], o.y + r * dy[type1]);
    }
    point mid() const {
        point v = (a + b) / 2 - o;
        return o + v.tolen(r);
    }
};

double dist_point_line(const point &p, const point &a, const point &b) {
    return abs(cross(p, a, b)) / dist(a, b);
}

bool point_on_seg(const point &p, const point &a, const point &b) {
    return sgn(dot(p, a, b)) < 0;
}

bool inter_seg_seg(const point &a, const point &b, const point &c, const point &d) {
    double s1 = cross(a, b, c);
    double s2 = cross(a, b, d);
    if (sgn(s2 - s1) == 0)
        return false;
    point p = (c * s2 - d * s1) / (s2 - s1);
    return point_on_seg(p, a, b) && point_on_seg(p, c, d);
}

int n;
point ps, pe;

vector <rt> rect;
vector <rt> rect_ex;

vector <double> r;
vector <double> h;

vector <point> pt[400];
vector <pair <int, int> > tangent;

bool point_in_circle(const point &p, const circle &c) {
    return sgn(dist2(p, c.o) - sqr(c.r)) < 0;
}

bool point_in_rect(const point &p, const rt &r) {
    return sgn(p.x - r.xmin) > 0 && sgn(p.x - r.xmax) < 0
        && sgn(p.y - r.ymin) > 0 && sgn(p.y - r.ymax) < 0;
}

bool point_on_arc(const point &p, const arc &a) {
    return sgn(dot(p, a.a, a.b)) < 0;
}

bool point_on_quater_arc(const point &p, const arc &a) {
    return sgn(dot(p, a.a, a.b)) <= 0;
}

bool inter_seg_rect(const point &a, const point &b, const rt &rect) {
    if (point_in_rect(a, rect))
        return true;
    for (int i = 0; i < 4; i++)
        if (inter_seg_seg(a, b, rect.p[i], rect.p[NEXT(i, 4)]))
            return true;
    return false;
}

bool inter_circle_line(const circle &c, const point &a, const point &b, point &p1, point &p2) {
    double h;
    if (sgn((h = dist_point_line(c.o, a, b)) - c.r) >= 0)
        return false;
    double l = sqrt(sqr(c.r) - sqr(h));
    point v;
    if (sgn(cross(a, c.o, b)) < 0)
        v = a - b;
    else
        v = b - a;
    p1 = c.o + v.turn_left().tolen(h) + v.tolen(l);
    p2 = c.o + v.turn_left().tolen(h) - v.tolen(l);

    return true;
}

bool inter_seg_circle(const point &a, const point &b, const circle &c) {
    point p1, p2;
    if (!inter_circle_line(c, a, b, p1, p2))
        return false;
    return point_on_seg(p1, a, b) ||
           point_on_seg(p2, a, b) ||
           point_in_circle((a + b) / 2, c);
}

bool ok_point(const point &a, const int &i) {
    if (i >= 0 && !point_on_quater_arc(a, arc(rect[i / 4].p[i % 4], r[i / 4], i % 4)))
        return false;
    for (int p = 0; p < 4 * n; p++)
        if (point_in_circle(a, circle(rect[p / 4].p[p % 4], r[p / 4])))
            return false;
    for (int p = 0; p < SZ(rect_ex); p++)
        if (point_in_rect(a, rect_ex[p]))
            return false;
    return true;
}

bool ok_seg(const point &a, const point &b) {
    for (int i = 0; i < SZ(rect_ex); i++)
        if (inter_seg_rect(a, b, rect_ex[i]))
            return false;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            if (inter_seg_circle(a, b, circle(rect[i].p[j], r[i])))
                return false;
    return true;
}

bool inter_arc_seg(const arc &a, const point &s, const point &e) {
    point p1, p2;
    if (!inter_circle_line(circle(a.o, a.r), s, e, p1, p2))
        return false;

    return ((point_on_seg(p1, s, e) && point_on_arc(p1, a))) ||
            (point_on_seg(p2, s, e) && point_on_arc(p2, a));
}

bool inter_arc_rect(const arc &a, const rt &rect) {
    if (point_in_rect(a.a, rect))
        return true;
    for (int i = 0; i < 4; i++) {
        if (inter_arc_seg(a, rect.p[i], rect.p[NEXT(i, 4)]))
            return true;
    }
    return false;
}

bool inter_circle_circle(const circle &a, const circle &b, point &p1, point &p2) {
    double d = dist(a.o, b.o);
    if (sgn(d - a.r - b.r) >= 0)
        return false;
    point v = b.o - a.o;
    double l = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
    double t = sqrt(sqr(a.r) - sqr(l));
    p1 = a.o + v.turn_left().tolen(t) + v.tolen(l);
    p2 = a.o + v.turn_right().tolen(t) + v.tolen(l);
    return true;
}

bool inter_arc_circle(const arc &a, const circle &c) {
    point p1, p2;
    if (!inter_circle_circle(circle(a.o, a.r), c, p1, p2))
        return false;
    return point_on_arc(p1, a) || point_on_arc(p2, a) || point_in_circle(a.mid(), c);
}

bool ok_arc(const arc &a) {
    for (int i = 0; i < SZ(rect_ex); i++)
        if (inter_arc_rect(a, rect_ex[i]))
            return false;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            if (inter_arc_circle(a, circle(rect[i].p[j], r[i])))
                return false;
    return true;
}

void tangent_point_circle(int &cnt_pt, const point &a, const circle &c,
    vector <point> &t1, vector <pair <int, int> > &tangent, const int &ia, const int &ib) {

    point b = c.o;
    double r = c.r;
    
    if (ia >= 0 && !ok_point(a, ia))
        return;
    double l2ab = dist2(a, b);