自动搬运

查看原文

来自洛谷，原作者为

	wind_boy When that I was and a little tiny boy, with hey, ho, the wind and the rain...

搬运于2025-08-24 22:48:04，当前版本为作者最后更新于2023-06-22 17:00:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

妙妙题！

• 黎曼和近似

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

$$\int_A^Bf(x)\approx \sum_{i=0}^{n-1}\frac{B-A}nf(A+\frac{i(B-A)}n+\frac1{2n}) $$

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

定理：如果 $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);
}