1 条题解

  • 1
    @ 2022-7-20 21:59:20
    #include<cstdio>
    #include<cmath>
    #define EPS 1e-7
    
    double alpha;
    int n;
    struct circle
    {
    	double x, r;
    	//x为投影圆心到树根的距离,r为半径 
    }p[1000];
    
    struct tan_line
    {
    	double k, b, left, right;
    	//f(x)=kx+b,x∈[left,right]
    }q[1000];
    
    double Gougu(double a, double b)//a是斜边 
    {
    	return sqrt(a*a - b * b);
    }
    
    void get_tan(int x, int y)
    {
    	if (fabs(p[x].r - p[y].r)<EPS)//实数比较记得带上EPS 
    	{
    		q[x].left = p[x].x;
    		q[x].right = p[y].x;
    		q[x].k = 0; q[x].b = p[x].r;
    		return;
    	}
    	double dx = p[y].x - p[x].x, dr = fabs(p[x].r - p[y].r);
    	//dx即图中的AC,dr即图中的AJ 
    	double ly, ry;
    	if (p[x].r>p[y].r)
    	{
    		q[x].left = p[x].x + p[x].r*dr / dx;//公切线左端 
    		q[x].right = p[y].x + (q[x].left - p[x].x)*p[y].r / p[x].r;//公切线右端 
    		ly = Gougu(p[x].r, q[x].left - p[x].x);//勾股定理求F(left)
    		ry = Gougu(p[y].r, q[x].right - p[y].x);//勾股定理求F(right) 
    		q[x].k = (ly - ry) / (q[x].left - q[x].right);//求斜率 
    		q[x].b = ly - q[x].left*q[x].k;//求纵截距 
    	}
    	else//另一种情况,同理 
    	{
    		q[x].right = p[y].x - p[y].r*dr / dx;
    		q[x].left = p[x].x - (p[y].x - q[x].right)*p[x].r / p[y].r;
    		ly = Gougu(p[x].r, q[x].left - p[x].x);
    		ry = Gougu(p[y].r, q[x].right - p[y].x);
    		q[x].k = (ly - ry) / (q[x].left - q[x].right);
    		q[x].b = ly - q[x].left*q[x].k;
    	}
    }
    
    double F(double x)
    {
    	double ans = 0.0;
    	for (int i = 1; i <= n; ++i)
    	{
    		if (x<p[i].x + p[i].r&&x>p[i].x - p[i].r)//x在这一段内 
    		{
    			//迭代答案 
    			ans = ans>Gougu(p[i].r, x - p[i].x) ? ans : Gougu(p[i].r, x - p[i].x);
    		}
    	}
    	for (int i = 1; i <= n; ++i)
    	{
    		if (x >= q[i].left&&x <= q[i].right)//x在这一段内 
    		{
    			//迭代答案 
    			ans = ans>q[i].k*x + q[i].b ? ans : q[i].k*x + q[i].b;
    		}
    	}
    	return ans;
    }
    
    //三点Simpson法 
    double simpson(double a, double b)
    {
    	double c = a + (b - a) / 2.0;
    	return (b - a) * (F(a) + 4.0 * F(c) + F(b)) / 6.0;
    }
    
    //自适应Simpson公式 
    double asr(double a, double b, double ans)
    {
    	double c = a + (b - a) / 2.0;
    	double left = simpson(a, c), right = simpson(c, b);
    	if (fabs(left + right - ans) < EPS)
    	{
    		return left + right;
    	}
    	else
    	{
    		return asr(a, c, left) + asr(c, b, right);
    	}
    }
    
    int main()
    {
    	scanf("%d %lf", &n, &alpha);
    	alpha = 1.0 / tan(alpha);//我们只会用到cot(alpha) 
    	scanf("%lf", &p[1].x);
    	p[1].x *= alpha;
    	for (int i = 2; i <= n + 1; ++i)
    	{
    		scanf("%lf", &p[i].x);
    		p[i].x *= alpha;
    		p[i].x += p[i - 1].x;
    	}
    	for (int i = 1; i <= n; ++i)
    		scanf("%lf", &p[i].r);
    	++n;
    	p[n].r = 0.0;//树顶是圆锥 
    	for (int i = 1; i <= n - 1; ++i)
    	{
    		get_tan(i, i + 1);//求i与i+1间的切线 
    	}
    
    	//迭代整个影子的最低点和最高点 
    	double ll = p[1].x - p[1].r, rr = p[n].x;
    	for (int i = 1; i <= n; ++i)
    	{
    		rr = rr>(p[i].x + p[i].r) ? rr : (p[i].x + p[i].r);
    		ll = ll<(p[i].x - p[i].r) ? ll : (p[i].x - p[i].r);
    	}
    	printf("%.2lf\n", 2.0*asr(ll, rr, simpson(ll, rr)));
    	//我们只算了影子的一半,所以还要乘2 
    	return 0;
    }
    
    • 1

    信息

    ID
    3138
    时间
    1000ms
    内存
    125MiB
    难度
    7
    标签
    递交数
    1
    已通过
    1
    上传者