题目传送。给定N(3 <= N <= 8000)个顶点的多边形P,积分区域D = \{(x, y) | (x, y) in P\},求解\iint_{D} (x + y)\mathrm{d}x\mathrm{d}y。好纯粹的数学题!首先,粗略地回顾了下二重积分,看到这样一个问题:假设有一薄平面,占有xoy平面上的闭区域D,点(x, y)处的面密度为\rho(x, y),假定\rho(x, y)D上连续,求薄平面的质量。

好熟悉的应用!对应本题,面密度是\rho(x, y) = x + y,积分区域是多边形,那么假设P的重心为(gx, gy),根据重心的定义,可得gx = \frac{\iint_{D}x\mathrm{d}x\mathrm{d}y}{S}, gy = \frac{\iint_{D}y\mathrm{d}x\mathrm{d}y}{S},其中SP的面积。再由积分的性质,可得\iint_{D}(x + y)\mathrm{d}x\mathrm{d}y = (gx + gy) * S。而多边形有向面积S,重心(gx, gy)都可以根据顶点坐标和叉积在O(N)时间内求解。