【BZOJ-1502】月下柠檬树 计算几何 + 自适应Simpson积分

时间:2023-12-11 08:09:20

1502: [NOI2005]月下柠檬树

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit:
1017  Solved: 562
[Submit][Status][Discuss]

Description

【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分

Input

文件的第1行包含一个整数n和一个实数alpha,表示柠檬树的层数和月亮的光线与地面夹角(单位为弧度)。第2行包含n+1个实数h0,h1,h2,…,hn,表示树离地的高度和每层的高度。第3行包含n个实数r1,r2,…,rn,表示柠檬树每层下底面的圆的半径。上述输入文件中的数据,同一行相邻的两个数之间用一个空格分隔。输入的所有实数的小数点后可能包含1至10位有效数字。

Output

输出1个实数,表示树影的面积。四舍五入保留两位小数。

Sample Input

2 0.7853981633
10.0 10.00
10.00
4.00 5.00

Sample Output

171.97

HINT

1≤n≤500,0.3

Source

Solution

一道计算集合比较蛋疼的题目

当时的正解应该是分类讨论+特判很多东西再直接求面积,但是发现这题非常适合辛普森积分所以就直接上了

那么先是辛普森积分的公式:【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分

对于某些不易计算曲线的一种近似方法,能自动调整精度,但误差较大(比较平滑的曲线非常适合)

具体的计算流程就是,计算[l,mid]以及[mid,r]与直接计算[l,r]的结果相比较,如果近似则返回[l,r]即可,否则可以分别递归细化

这种做法非常好卡,一种最简单的卡法:【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分这样一开始就会直接返回,然而递归下去才能求的更精确的值

---------------------------------------------------分割线---------------------------------------------------

首先我们考虑这题的投影,圆投下来,和之前完全一样,所以投影本质是一些圆和他们的公切线组成的图形求面积

【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分

发现其实是轴对称图形,所以可以考虑直接利用扫描线+自适应Simpson来做

扫描线被覆盖部分的长度的函数F(x)在这个图形的区间中是连续的,因此不必考虑将整个图形拆成若干个一坨一坨的图形再求积分,少了不少细节。

无论扫描线在何处,它被覆盖的部分也是永远是连续的,因此可以暴力找每个圆是否和扫描线有交,每条公切线段是否和扫描线有交,然后取扫描线被覆盖长度的最大值即可

那么至于求公切线,比较简单,给出详细方法:

【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分

首先我们得到:$l=C_{i+1}.O.x-C_{i+1}.O.x$
那么我们可以算出:$sin\alpha = (R-r)/l$,$cos\alpha = \sqrt{1-sin^2\alpha}$(考虑从$C_{i+1}.O$向$R$做垂线)
那么可以算出切点:

$C_{i}.A=(C_{i}.O.x+R*sin\alpha,R*cos\alpha)$
$C_{i+1}.A=(C_{i+1}.O.x+r*sin\alpha,r*cos\alpha)$

这题的细节比较麻烦,注意特判圆被另一个圆直接覆盖的情况

---------------------------------------------------分割线---------------------------------------------------

这道题还需要注意一下精度问题

个人测试:eps=1e-5是可行最优

【BZOJ-1502】月下柠檬树       计算几何 + 自适应Simpson积分

eps=1e-12   --> 5s

eps=1e-8     --> 1s

eps=1e-5     --> 0.5s

eps=1e-3/-4 --> Wrong_Answer

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 1010
double alpha;
int N,num;
#define INF 1e12
#define eps 1e-5
struct Point
{
double x,y;
Point (double X=,double Y=) {x=X; y=Y;}
};
struct Circle
{
double r;
Point c;
Circle(Point C=(Point){,},double R=) {c=C; r=R;}
}C[MAXN];
struct Line
{
Point s,t;
double k,b;
Line(Point S=(Point){,},Point T=(Point){,})
{
s=S,t=T;
if (s.x>t.x) swap(s,t);
k=(s.y-t.y)/(s.x-t.x);
b=s.y-k*s.x;
}
double f(double x) {return k*x+b;}
}l[MAXN];
int dcmp(double x) {if (fabs(x)<eps) return ; return x<? -:;}
double F(double x)
{
double re=;
for (int i=; i<=N; i++) //枚举圆是否与扫描线有交
{
double d=fabs(x-C[i].c.x);
if (dcmp(d-C[i].r)>) continue;
double len=*sqrt(C[i].r*C[i].r-d*d);
re=max(re,len);
}
for (int i=; i<=num; i++) //枚举公切线
if (x>=l[i].s.x && x<=l[i].t.x) re=max(re,*l[i].f(x));
return re;
} //利用扫描线去判断
double Calc(double l,double r) {double mid=(l+r)/; return (F(l)+F(r)+F(mid)*)*(r-l)/;}
double Simpson(double l,double r,double now)
{
double mid=(l+r)/;
double x=Calc(l,mid),y=Calc(mid,r);
if (!dcmp(now-x-y)) return now;
else return Simpson(l,mid,x)+Simpson(mid,r,y);
}
void Solve()
{
double L=INF,R=-INF;
for (int i=; i<=N+; i++)
L=min(L,C[i].c.x-C[i].r),R=max(R,C[i].c.x+C[i].r);
// printf("%lf\n%lf\n",L,R);
for (int i=; i<=N; i++)
{
double d=C[i+].c.x-C[i].c.x;
if (dcmp(d-fabs(C[i].r-C[i+].r))<) continue; //特判小圆被大圆覆盖的情况
double sina=(C[i].r-C[i+].r)/d,cosa=sqrt(-sina*sina);
l[++num]=(Line){(Point){C[i].c.x+C[i].r*sina,C[i].r*cosa},(Point){C[i+].c.x+C[i+].r*sina,C[i+].r*cosa}};
}
printf("%.2lf\n",Simpson(L,R,Calc(L,R)));
}
int main()
{
scanf("%d%lf",&N,&alpha);
double h,r;
for (int i=; i<=N+; i++)
scanf("%lf",&h),
C[i]=(Circle){((Point){(h/tan(alpha))+C[i-].c.x,}),};
for (int i=; i<=N; i++)
scanf("%lf",&r),C[i].r=r;
// for (int i=1; i<=N+1; i++)
// printf("%d %.2lf %.2lf\n",i,C[i].c.x,C[i].r);
Solve();
return ;
}

晚上颓这道‘模版题’简直不要太爽,来个人求一下我的心里阴影面积吧QAQ