卧薪尝胆,厚积薄发。
NOI2005 月下柠檬树
Date: Fri Dec 14 13:46:07 CST 2018 In Category: NoCategory

Description:

给一堆摞在一起的圆台和圆锥,求他们投影的面积。
$1\leqslant n\leqslant 500$

Solution:

最后的图形就是一堆圆还有这些圆的切线,圆的切线可以用相似三角形求,最后用自适应辛普森积分求即可。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n;
double alpha;
#define MAXN 510
double r[MAXN],h[MAXN];
struct circ
{
double x,r;
}c[MAXN];
struct line
{
double k,b;
double l,r;
}l[MAXN];
const double eps = 1e-10;
line build_line(circ a,circ b)
{
if((a.x - a.r <= b.x - b.r && a.x + a.r >= b.x + b.r) || (b.x - b.r <= a.x - a.r && b.x + b.r >= a.x + a.r))
{
return (line){0,0,0,0};
}
line res;
if(fabs(a.r - b.r) <= eps)
{
res.l = a.x;res.r = b.x;
res.k = 0;res.b = a.r;
return res;
}
else
{
double x = (b.r * a.x - b.x * a.r) / (b.r - a.r);
double xa,ya,xb,yb;
if(fabs(a.x - x) > eps)xa = a.x - a.r * a.r / (a.x - x);
else xa = a.x;
ya = sqrt(a.r * a.r - (a.x - xa) * (a.x - xa));
if(fabs(b.x - x) > eps)xb = b.x - b.r * b.r / (b.x - x);
else xb = b.x;
yb = sqrt(b.r * b.r - (b.x - xb) * (b.x - xb));
res.l = xa;res.r = xb;
res.k = (ya - yb) / (xa - xb);
res.b = yb - xb * res.k;
return res;
}
}
double f(double x)
{
double res = 0;
for(int i = 1;i <= n;++i)
{
if(x <= c[i].x - c[i].r || x > c[i].x + c[i].r)continue;
res = max(res,sqrt(c[i].r * c[i].r - (x - c[i].x) * (x - c[i].x)));
}
for(int i = 1;i < n;++i)
{
if(x < l[i].l || x > l[i].r)continue;
res = max(res,l[i].k * x + l[i].b);
}
return res;
}
double simpson(double l,double r)
{
return (r - l) * (f(l) + 4 * f((l + r) / 2) + f(r)) / 6;
}
double solve(double l,double r,double k)
{
double mid = (l + r) / 2;
double L = simpson(l,mid),R = simpson(mid,r);
if(fabs(L + R - k) <= eps)return k;
else return solve(l,mid,L) + solve(mid,r,R);
}
int main()
{
scanf("%d%lf",&n,&alpha);
for(int i = 1;i <= n + 1;++i)scanf("%lf",&h[i]);
for(int i = 1;i <= n;++i)scanf("%lf",&r[i]);
r[++n] = 0;
double H = 0;
for(int i = 1;i <= n;++i)
{
H += h[i];
c[i].x = H / tan(alpha);
c[i].r = r[i];
}
for(int i = 1;i < n;++i)l[i] = build_line(c[i],c[i + 1]);
double l = 10000000,r = 0;
for(int i = 1;i <= n;++i)
{
l = min(l,c[i].x - c[i].r);
r = max(r,c[i].x + c[i].r);
}
printf("%.2lf\n",solve(l,r,simpson(l,r)) * 2);
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡