P9405 题解

wind_boy · 2023-06-22 17:00:33 · 题解

妙妙题！

• 黎曼和近似

根据定积分的定义，我们将区间 [A,B] 分割成 n 份，对每一份用区间中点处的 f 值来近似平均值，从而近似整个区间的值. 形式化地：

那么，黎曼和近似的精度是多少呢？

定理：如果 f 在 [A,B] 内任意阶可导，黎曼和近似的绝对误差在最坏情况下不超过 \dfrac{K(B-A)^3}{24n^2}，其中 K 为 |f^{(2)}(x)| 在 [A,B] 中的最大值.

证明略。

题解：

众所周知 \int_0^{\frac\pi2}\cos\theta\,\text{d}\theta=1。

也就是说，将一条线段映射到一条斜率为 \tan \theta\pod{0\leq \theta\leq \pi} 的直线上的长度的积分为该线段长度的 2 倍，即 \int_0^{\pi}l\,|\cos\theta|\,\text{d}\theta=2l。

考虑黎曼求和。我们选取 m 个均匀的角度 \alpha_1,\alpha_2,\cdots,\alpha_m，将这些线段依次映射到 y=\tan{\alpha_i}\cdot x 上，于是就转化为了一维问题。

对于一维问题，我们只需将其排序然后做前缀后缀和即可。

根据上述定理，其精度误差为 O(m^{-2})，因此取 m=\Theta(\epsilon^{-0.5}) 即可。

时间复杂度 O(n\epsilon^{-0.5}\log n)。

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define ld double
using namespace std;
const int N=100007,B=30;
const ld PI=acos(-1.0);
int n,w[N];ld ans[N],v[N];
struct point{int x,y;}p[N];
bool cmp(int a,int b){return v[a]<v[b];}
int main()
{
    scanf("%d",&n);
    fo(i,1,n) scanf("%d%d",&p[i].x,&p[i].y);
    fo(T,0,B-1)
    {
        ld c=cos(PI/B*(T+0.5)),s=sin(PI/B*(T+0.5)),sum=0;
        fo(i,1,n) v[i]=p[i].x*c-p[i].y*s,w[i]=i;//旋转后映射到x轴
        sort(w+1,w+n+1,cmp);
        fo(i,1,n) ans[w[i]]+=v[w[i]]*(i-1)-sum,sum+=v[w[i]];
        sum=0;
        fd(i,n,1) ans[w[i]]+=sum-v[w[i]]*(n-i),sum+=v[w[i]];
    }
    fo(i,1,n) printf("%.6lf\n",ans[i]*PI/B/2);
}