Chlience

【题解】BZOJ 1502 [NOI2005]月下柠檬树
Problem给定一棵由圆锥和圆台依次组成的一棵树,求以 $\alpha$ 角度照过来的平行光留下的阴影面积Tho...
扫描右侧二维码阅读全文
20
2019/01

【题解】BZOJ 1502 [NOI2005]月下柠檬树

Problem

给定一棵由圆锥和圆台依次组成的一棵树,求以 $\alpha$ 角度照过来的平行光留下的阴影面积

Thought

做这种题空间想象能力要强啊...

首先对于一个圆,其投影显然是一个圆,且半径不变,圆心位置和角度,高度有关
那么对于一个圆锥的话,可以将区分为两部分:圆和点,和点到圆的切线
对于一个圆台,自然就是两个圆以及其公切线

那么对于每一段,将其分成三个图形:两个圆+梯形,其中圆可能退化为点,梯形可能退化为三角形

圆由于其半径不变,只需要求圆心,这个很好搞
如何求梯形呢?

geogebra-export.png

显然有 $\frac{r1}{\cos\alpha}-\frac{r2}{\cos\alpha}=dis$

稍加变形可得 $\arccos(\frac{r1-r2}{dis})=\alpha$

那么就可以求得 $B,D$ 坐标,向 $x$ 轴引垂线画出梯形即可

但是这个题目很容易 $T$ 掉,从 $1.5s$ 卡到 $0.1s$ 的我表示能不用向量就别用向量
本地 $O2$ 跑的很快但是 $BZOJ$ 就...

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const double eps = 1e-8;
#define mid ((l + r) / 2)
#define lmid ((l + mid) / 2)
#define rmid ((mid + r) / 2)
pair<double, double> sta[N * 2];
int top;
struct Vector {
    double x, y;
    Vector operator + (const Vector a) const {return Vector{x + a.x, y + a.y};}
    Vector operator - (const Vector a) const {return Vector{x - a.x, y - a.y};}
    double operator * (const Vector a) const {return x * a.y - y * a.x;}
    Vector operator * (const double a) const {return Vector{x * a, y * a};}
};
struct Trapezoid {
    Vector s, t;
}t[N];
int n, t_cnt;
double alpha;
double p[N], r[N];
double min_x, max_x;
void addTrapezoid(double, double, double, double);
double crossPos(double, double, double);
bool crossCheck(Vector, Vector, double);
Vector crossPos(Vector, Vector, Vector, Vector);
double f(double);
double simpson(double, double, double, double, double);
int main() {
    scanf("%d %lf", &n, &alpha);
    for(int i = 1; i <= n + 1; ++ i) {
        scanf("%lf", &p[i]);
        p[i] += p[i - 1];
    }
    for(int i = 1; i <= n + 1; ++ i)
        p[i] /= tan(alpha);
    min_x = max_x = p[n + 1];
    for(int i = 1; i <= n; ++ i) {
        scanf("%lf", &r[i]);
        min_x = min(min_x, p[i] - r[i]);
        max_x = max(max_x, p[i] + r[i]);
    }
    for(int i = 1 ; i <= n; ++ i)
        addTrapezoid(p[i], r[i], p[i + 1], r[i + 1]);
    printf("%.2f\n", simpson(min_x, max_x, f(min_x), f((min_x + max_x) / 2), f(max_x)) - eps);
    return 0;
}
void addTrapezoid(double p1, double r1, double p2, double r2) {
    if(p2 - p1 - r2 + r1 <= eps) return;
    double beta = acos((r1 - r2) / (p2 - p1));
    t[++ t_cnt] = {{p1 + r1 * cos(beta), r1 * sin(beta)}, {p2 + r2 * cos(beta), r2 * sin(beta)}};
}
double crossPos(double p, double r, double x) {
    double dis = fabs(p - x);
    return sqrt(r * r - dis * dis);
}
bool crossCheck(Vector s, Vector e, double x) {return max(s.x, e.x) - x >= eps && min(s.x, e.x) - x <= eps;}
Vector crossPos(Vector p1, Vector v1, Vector p2, Vector v2) {return v1 * (((p2 - p1) * v2) / (v1 * v2)) + p1;}
double f(double x) {
    top = 0;
    Vector a = {x, - 100}, b = {x, 100};
    double maxpos = 0;
    for(int i = 1; i <= n; ++ i) {
        if(p[i] - r[i] - x <= eps && p[i] + r[i] - x >= eps) {
            double pos = crossPos(p[i], r[i], x);
            if(pos > maxpos) maxpos = pos;
        }
    }
    for(int i = 1; i <= t_cnt; ++ i) {
        if(crossCheck(t[i].s, t[i].t, x)) {
            Vector pos = crossPos(t[i].s, t[i].t - t[i].s, a, b - a);
            if(pos.y > maxpos) maxpos = pos.y;
        }
    }
    return maxpos * 2;
}
double simpson(double l, double r, double fl, double fmid, double fr) {
    double flmid = f(lmid), frmid = f(rmid);
    double L = (mid - l) * (fl + fmid + 4 * flmid) / 6;
    double R = (r - mid) * (fmid + fr + 4 * frmid) / 6;
    double ANS = (r - l) * (fl + fr + 4 * fmid) / 6;
    if(fabs(ANS - L - R) <= eps)
        return ANS;
    else
        return simpson(l, mid, fl, flmid, fmid) + simpson(mid, r, fmid, frmid, fr);
}
Last modification:January 20th, 2019 at 04:39 pm

Leave a Comment