题解

2 条题解

  • 0
    @ 2014-01-27 21:04:23

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;

    const double eps = 1e-08;
    const double invalid = 1e+50;
    const double pi = 3.14159265358979;
    inline bool valid (double a)
    {
    if (a < 1e+40) return true;
    else return false;
    }
    inline int fi (double a)
    {
    if (a > eps) return 1;
    else if (a >= -eps) return 0;
    else return -1;
    }
    inline double ssqrt (double x)
    {
    if (fi(x) <= 0) return 0;
    else return sqrt(x);
    }
    inline double sacos (double x)
    {
    if (fi(x + 1) <= 0) return pi;
    else if (fi(x - 1) >= 0) return 0;
    else return acos(x);
    }
    double nul (double x, double x0, double r) { return 0; }
    double cir (double x, double x0, double r) { return ssqrt(r * r - (x - x0) * (x - x0)); }
    double lin (double x, double k, double b) { return k * x + b; }
    typedef pair<double, double> prd;
    prd bin (double a, double b, double c)
    {
    double delta = b * b - 4 * a * c;
    if (fi(delta) == -1) return prd(invalid, invalid);
    else return prd((-b + ssqrt(delta)) / (2 * a), (-b - ssqrt(delta)) / (2 * a));
    }
    double prlarea (double x0, double r, double x)
    {
    double st = sacos((x0 - x) / r);
    return (st - sin(st * 2) / 2) * (r * r / 2);
    }
    class segment
    {
    public:
    double k, b, l, r;
    segment (void) {}
    segment (double x0, double y0, double x1, double y1)
    {
    k = (y1 - y0) / (x1 - x0);
    b = y0 - k * x0;
    l = min(x0, x1), r = max(x0, x1);
    }
    bool online (double x) const { return fi(l - x) <= 0 && fi(x - r) <= 0; }
    double intersect (const segment& s) const
    {
    double ans = (s.b - b) / (k - s.k);
    if (online(ans) && s.online(ans)) return ans;
    else return invalid;
    }
    };
    class circle
    {
    public:
    double x, r;
    circle (void) {}
    circle (double x0, double r0) : x(x0), r(r0) {}
    double intersect (const circle& c) const
    {
    if (fi(fabs(c.x - x) - (c.r + r)) >= 0) return invalid;
    else if (fi(fabs(c.x - x) - fabs(c.r - r) <= 0)) return invalid;
    else return ((r * r - x * x) - (c.r * c.r - c.x * c.x)) / (2 * c.x - 2 * x);
    }
    prd intersect (const segment& s) const
    {
    prd ans = bin(1 + s.k * s.k, 2 * s.k * s.b - 2 * x, s.b * s.b + x * x - r * r);
    if (valid(ans.first)) if (!s.online(ans.first)) ans.first = invalid;
    if (valid(ans.second)) if (!s.online(ans.second)) ans.second = invalid;
    return ans;
    }
    segment cmtangent (const circle& c) const
    {
    double ca = (r - c.r) / (c.x - x);
    double sa = ssqrt(1 - ca * ca);
    return segment(x + r * ca, r * sa, c.x + c.r * ca, c.r * sa);
    }
    };
    class func
    {
    private:
    double (*f)(double, double, double);
    double arg1, arg2;
    public:
    func (void) : f(nul) {}
    func (const segment& a) : f(lin), arg1(a.k), arg2(a.b) {}
    func (const circle& a) : f(cir), arg1(a.x), arg2(a.r) {}
    double value (double x) { return (*f)(x, arg1, arg2); }
    double weiss (double a, double b)
    {
    if (f == nul) return 0;
    else if (f == cir) return prlarea(arg1, arg2, b) - prlarea(arg1, arg2, a);
    else return (value(b) + value(a)) * (b - a) / 2;
    }
    };
    class interval
    {
    public:
    double l, r;
    func f;
    interval (void) {}
    interval (double l0, double r0) : l(l0), r(r0) {}
    void load (func ff)
    {
    int t;
    if (t = fi(ff.value(l) - f.value(l)))
    {
    if (t == 1) f = ff;
    return;
    }
    else if (t = fi(ff.value(r) - f.value(r)))
    {
    if (t == 1) f = ff;
    return;
    }
    t = fi(ff.value((l + r) / 2) - f.value((l + r) / 2));
    if (t == 1) f = ff;
    }
    double area (void) { return f.weiss(l, r); }
    };
    circle cs[510]; segment gs[510];
    double lsh[500010], lsht[500010]; int lshmr;
    interval lqr[500010];
    void lshinit (void)
    {
    sort(lsh, lsh + lshmr);
    int cnt = 0;
    for (int i = 0; i < lshmr; i++)
    {
    if (i == 0 || fi(lsh[i] - lsh[i - 1]))
    lsht[cnt++] = lsh[i];
    } lshmr = cnt;
    }
    int place (double a)
    {
    int st = 0, ed = lshmr, mid = 0;
    while (ed - st > 1)
    {
    mid = (st + ed) >> 1;
    if (fi(lsht[mid] - a) > 0) ed = mid;
    else st = mid;
    } return st;
    }
    int main ()
    {
    int n, st, ed; double alpha, h[510], r[510], x, ans;
    prd res; segment s;
    scanf("%d %lf", &n, &alpha); n++;
    for (int i = 0; i < n; i++) scanf("%lf", &h[i]);
    for (int i = 0; i < n - 1; i++) scanf("%lf", &r[i]);
    for (int i = 1; i < n; i++) h[i] += h[i - 1];
    for (int i = 0; i < n - 1; i++)
    {
    x = h[i] / tan(alpha);
    cs[i] = circle(x, r[i]);
    }
    cs[n - 1] = circle(h[n - 1] / tan(alpha), 0);
    for (int i = 0; i < n - 1; i++)
    {
    if (fi(fabs(cs[i].x - cs[i + 1].x) - fabs(cs[i].r - cs[i + 1].r)) == 1)
    {
    s = cs[i].cmtangent(cs[i + 1]);
    gs[i] = s;
    }
    }
    lshmr = 0;
    for (int i = 0; i < n - 1; i++)
    {
    lsh[lshmr++] = cs[i].x - cs[i].r;
    lsh[lshmr++] = cs[i].x + cs[i].r;
    }
    lsh[lshmr++] = cs[n - 1].x;
    for (int i = 0; i < n - 1; i++)
    {
    lsh[lshmr++] = gs[i].l;
    lsh[lshmr++] = gs[i].r;
    }
    for (int i = 0; i < n - 1; i++)
    {
    for (int j = i + 1; j < n - 1; j++)
    {
    x = cs[i].intersect(cs[j]);
    if (valid(x)) lsh[lshmr++] = x;
    }
    for (int j = 0; j < n - 1; j++)
    {
    res = cs[i].intersect(gs[j]);
    if (valid(res.first)) lsh[lshmr++] = res.first;
    if (valid(res.second)) lsh[lshmr++] = res.second;
    }
    }
    for (int i = 0; i < n - 1; i++)
    {
    for (int j = i + 1; j < n - 1; j++)
    {
    x = gs[i].intersect(gs[j]);
    if (valid(x)) lsh[lshmr++] = x;
    }
    }
    lshinit();
    for (int i = 0; i < lshmr - 1; i++)
    lqr[i] = interval(lsht[i], lsht[i + 1]);
    for (int i = 0; i < n - 1; i++)
    {
    st = place(cs[i].x - cs[i].r);
    ed = place(cs[i].x + cs[i].r);
    for (int j = st; j < ed; j++)
    lqr[j].load(func(cs[i]));
    }
    for (int i = 0; i < n - 1; i++)
    {
    st = place(gs[i].l);
    ed = place(gs[i].r);
    for (int j = st; j < ed; j++)
    lqr[j].load(func(gs[i]));
    }
    ans = 0;
    for (int i = 0; i < lshmr - 1; i++)
    ans += lqr[i].area();
    printf("%.2f\n", ans * 2);
    return 0;
    }

  • 0
    @ 2014-01-27 21:01:51

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;

    const double eps = 1e-08;
    const double invalid = 1e+50;
    const double pi = 3.14159265358979;
    inline bool valid (double a)
    {
    if (a < 1e+40) return true;
    else return false;
    }
    inline int fi (double a)
    {
    if (a > eps) return 1;
    else if (a >= -eps) return 0;
    else return -1;
    }
    inline double ssqrt (double x)
    {
    if (fi(x) <= 0) return 0;
    else return sqrt(x);
    }
    inline double sacos (double x)
    {
    if (fi(x + 1) <= 0) return pi;
    else if (fi(x - 1) >= 0) return 0;
    else return acos(x);
    }
    double nul (double x, double x0, double r) { return 0; }
    double cir (double x, double x0, double r) { return ssqrt(r * r - (x - x0) * (x - x0)); }
    double lin (double x, double k, double b) { return k * x + b; }
    typedef pair<double, double> prd;
    prd bin (double a, double b, double c)
    {
    double delta = b * b - 4 * a * c;
    if (fi(delta) == -1) return prd(invalid, invalid);
    else return prd((-b + ssqrt(delta)) / (2 * a), (-b - ssqrt(delta)) / (2 * a));
    }
    double prlarea (double x0, double r, double x)
    {
    double st = sacos((x0 - x) / r);
    return (st - sin(st * 2) / 2) * (r * r / 2);
    }
    class segment
    {
    public:
    double k, b, l, r;
    segment (void) {}
    segment (double x0, double y0, double x1, double y1)
    {
    k = (y1 - y0) / (x1 - x0);
    b = y0 - k * x0;
    l = min(x0, x1), r = max(x0, x1);
    }
    bool online (double x) const { return fi(l - x) <= 0 && fi(x - r) <= 0; }
    double intersect (const segment& s) const
    {
    double ans = (s.b - b) / (k - s.k);
    if (online(ans) && s.online(ans)) return ans;
    else return invalid;
    }
    };
    class circle
    {
    public:
    double x, r;
    circle (void) {}
    circle (double x0, double r0) : x(x0), r(r0) {}
    double intersect (const circle& c) const
    {
    if (fi(fabs(c.x - x) - (c.r + r)) >= 0) return invalid;
    else if (fi(fabs(c.x - x) - fabs(c.r - r) <= 0)) return invalid;
    else return ((r * r - x * x) - (c.r * c.r - c.x * c.x)) / (2 * c.x - 2 * x);
    }
    prd intersect (const segment& s) const
    {
    prd ans = bin(1 + s.k * s.k, 2 * s.k * s.b - 2 * x, s.b * s.b + x * x - r * r);
    if (valid(ans.first)) if (!s.online(ans.first)) ans.first = invalid;
    if (valid(ans.second)) if (!s.online(ans.second)) ans.second = invalid;
    return ans;
    }
    segment cmtangent (const circle& c) const
    {
    double ca = (r - c.r) / (c.x - x);
    double sa = ssqrt(1 - ca * ca);
    return segment(x + r * ca, r * sa, c.x + c.r * ca, c.r * sa);
    }
    };
    class func
    {
    private:
    double (*f)(double, double, double);
    double arg1, arg2;
    public:
    func (void) : f(nul) {}
    func (const segment& a) : f(lin), arg1(a.k), arg2(a.b) {}
    func (const circle& a) : f(cir), arg1(a.x), arg2(a.r) {}
    double value (double x) { return (*f)(x, arg1, arg2); }
    double weiss (double a, double b)
    {
    if (f == nul) return 0;
    else if (f == cir) return prlarea(arg1, arg2, b) - prlarea(arg1, arg2, a);
    else return (value(b) + value(a)) * (b - a) / 2;
    }
    };
    class interval
    {
    public:
    double l, r;
    func f;
    interval (void) {}
    interval (double l0, double r0) : l(l0), r(r0) {}
    void load (func ff)
    {
    int t;
    if (t = fi(ff.value(l) - f.value(l)))
    {
    if (t == 1) f = ff;
    return;
    }
    else if (t = fi(ff.value(r) - f.value(r)))
    {
    if (t == 1) f = ff;
    return;
    }
    t = fi(ff.value((l + r) / 2) - f.value((l + r) / 2));
    if (t == 1) f = ff;
    }
    double area (void) { return f.weiss(l, r); }
    };
    circle cs[510]; segment gs[510];
    double lsh[500010], lsht[500010]; int lshmr;
    interval lqr[500010];
    void lshinit (void)
    {
    sort(lsh, lsh + lshmr);
    int cnt = 0;
    for (int i = 0; i < lshmr; i++)
    {
    if (i == 0 || fi(lsh[i] - lsh[i - 1]))
    lsht[cnt++] = lsh[i];
    } lshmr = cnt;
    }
    int place (double a)
    {
    int st = 0, ed = lshmr, mid = 0;
    while (ed - st > 1)
    {
    mid = (st + ed) >> 1;
    if (fi(lsht[mid] - a) > 0) ed = mid;
    else st = mid;
    } return st;
    }
    int main ()
    {
    int n, st, ed; double alpha, h[510], r[510], x, ans;
    prd res; segment s;
    scanf("%d %lf", &n, &alpha); n++;
    for (int i = 0; i < n; i++) scanf("%lf", &h[i]);
    for (int i = 0; i < n - 1; i++) scanf("%lf", &r[i]);
    for (int i = 1; i < n; i++) h[i] += h[i - 1];
    for (int i = 0; i < n - 1; i++)
    {
    x = h[i] / tan(alpha);
    cs[i] = circle(x, r[i]);
    }
    cs[n - 1] = circle(h[n - 1] / tan(alpha), 0);
    for (int i = 0; i < n - 1; i++)
    {
    if (fi(fabs(cs[i].x - cs[i + 1].x) - fabs(cs[i].r - cs[i + 1].r)) == 1)
    {
    s = cs[i].cmtangent(cs[i + 1]);
    gs[i] = s;
    }
    }
    lshmr = 0;
    for (int i = 0; i < n - 1; i++)
    {
    lsh[lshmr++] = cs[i].x - cs[i].r;
    lsh[lshmr++] = cs[i].x + cs[i].r;
    }
    lsh[lshmr++] = cs[n - 1].x;
    for (int i = 0; i < n - 1; i++)
    {
    lsh[lshmr++] = gs[i].l;
    lsh[lshmr++] = gs[i].r;
    }
    for (int i = 0; i < n - 1; i++)
    {
    for (int j = i + 1; j < n - 1; j++)
    {
    x = cs[i].intersect(cs[j]);
    if (valid(x)) lsh[lshmr++] = x;
    }
    for (int j = 0; j < n - 1; j++)
    {
    res = cs[i].intersect(gs[j]);
    if (valid(res.first)) lsh[lshmr++] = res.first;
    if (valid(res.second)) lsh[lshmr++] = res.second;
    }
    }
    for (int i = 0; i < n - 1; i++)
    {
    for (int j = i + 1; j < n - 1; j++)
    {
    x = gs[i].intersect(gs[j]);
    if (valid(x)) lsh[lshmr++] = x;
    }
    }
    lshinit();
    for (int i = 0; i < lshmr - 1; i++)
    lqr[i] = interval(lsht[i], lsht[i + 1]);
    for (int i = 0; i < n - 1; i++)
    {
    st = place(cs[i].x - cs[i].r);
    ed = place(cs[i].x + cs[i].r);
    for (int j = st; j < ed; j++)
    lqr[j].load(func(cs[i]));
    }
    for (int i = 0; i < n - 1; i++)
    {
    st = place(gs[i].l);
    ed = place(gs[i].r);
    for (int j = st; j < ed; j++)
    lqr[j].load(func(gs[i]));
    }
    ans = 0;
    for (int i = 0; i < lshmr - 1; i++)
    ans += lqr[i].area();
    printf("%.2f\n", ans * 2);
    return 0;
    }

  • 1

信息

ID
1839
难度
5
分类
(无)
标签
递交数
95
已通过
34
通过率
36%
被复制
2
上传者